Last Updated: 22 Oct, 2021
Ninja and his Dominos
Moderate
Asked in companies
Ninja has ‘N’ dominos. He puts all of these dominos in a straight line. Each domino has two values on it, top value and bottom value. You are given two arrays ‘top’ and ‘bottom’ where ‘top[i]’ denotes the top value at the ‘i’th domino and ‘bottom[i]’ denotes the bottom value of the ‘i’th domino. ‘top[i]’ and ‘bottom[i]’ are independent of each other.
Ninja wants to arrange these dominos such that either the top part or the bottom part of all the dominos is the same, but he can do only one operation: i.e., Rotate the ‘i’th domino such that ‘top[i]’ now becomes ‘bottom[i]’ and ‘bottom[i]’ becomes ‘top[i]’.
Help Ninja find the minimum number of operations required.
If he cannot do so, print -1.
For Example :
‘N’ = 4, ‘top’ = {3, 5, 3, 1}, ‘bottom’ = {2, 3, 5, 3}.
Now in this example, if Ninja rotates the second and the fourth dominos, the top row will be {3, 3, 3, 3}. Hence the answer is 2.
Input Format :
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the number of dominos.
The second line of the test case contains an array of ‘N’ integers denoting the ‘top’ array.
The third line of the test case contains an array of ‘N’ integers denoting the ‘bottom’ array.
Output Format :
For each test case, print a single integer denoting the minimum number of rotations required.
Output for every query will be printed in a separate line.
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.
Constraints :
1 <= T <= 10
1 <= ‘N’ <= 2 * 10^5
1 <= ‘top[i]’, ‘bottom[i]’ <= 6
Time Limit: 1 second
Approaches
As the numbers are only from 1 to 6, we can check for every number whether the number is present in all the ‘N’ dominos at least on one side or not. If the current number is present on all the ‘N’ dominos we will then calculate the minimum rotations needed to make either the top or the bottom row the same.
The steps are as follows:
- Take 3 arrays ‘countTop’, ‘countBottom’ and ‘countBoth’ of size 7.
- Iterate through the loop from 0 to ‘N’ - 1(say iterator be i):
- Take an integer ‘a’ = ‘top[i]’ and an integer ‘b’ = ‘bottom[i]’.
- Update the ‘countTop[a]’ = ‘countTop[a]’ + 1.
- Update the ‘countBottom[b]’ = ‘countBottom[b]’ + 1.
- Check if ‘a’ is equal to ‘b’:
- Update ‘countBoth[a]’ = ‘countBoth[a]’ + 1.
- Take an integer ‘ans’ to store the final answer and initialize it with N + 1.
- Iterate through the loop from 1 to 6(say iterator be i):
- Check if ‘countTop[i]’ + countBottom[i]’ - ‘countBoth[i]’ == ‘N’:
- Update ‘ans’ = min(‘ans’, min(‘countTop[i]’, countBottom[i]’) - ‘countBoth’).
- Check if ‘countTop[i]’ + countBottom[i]’ - ‘countBoth[i]’ == ‘N’:
- Check if ‘ans’ equals N + 1:
- Return -1.
- Else:
- Return ‘ans’.