Ninja and his Dominos

Moderate
0/80
profile
Contributed by
0 upvote
Asked in companies
Google incDealShare.in

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 1 5 6 1
5 5 1 1 5
3
1 2 3
2 2 4
Sample Output 1 :
2
-1
Explanation For Sample Output 1 :
In the first test case, Ninja can rotate the third and fourth element to make the top row {1, 1, 1, 1, 1}. Hence the answer is 2.

In the second test case, there are no possible combinations of operations that can be performed to make either the top or the bottom part same. Hence the answer is -1.
Sample Input 2 :
2
6
6 4 6 2 6 6
5 6 3 6 2 4
1
4
5
Sample Output 2 :
2
0
Hint

Check for every element from 1 to 6 and find the minimum rotations needed.

Approaches (1)
Brute Force Approach

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:

  1. Take 3 arrays ‘countTop’, ‘countBottom’ and ‘countBoth’ of size 7.
  2. 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.
  3. Take an integer ‘ans’ to store the final answer and initialize it with N + 1.
  4. 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’).
  5. Check if ‘ans’ equals N + 1:
    • Return -1.
  6. Else:
    • Return ‘ans’.
Time Complexity

O(N). Where N is the total number of dominos Ninja has.


As we are iterating through all the dominos.

Hence, the time complexity is O(N).

Space Complexity

O( 1 ).


Since we are only taking 3 arrays of size 7, which is constant space. 

Hence the space complexity is O(1)

Code Solution
(100% EXP penalty)
Ninja and his Dominos
Full screen
Console