Minimum Card Flips

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in company
Google inc

Problem statement

You are at your friend’s birthday party and one of your friends decided to play a card game with some special type of cards. These cards can have numbers written on both sides.

You are given ‘N’ cards, each card contains some integer number between ‘1’ to ‘10’ written on both sides. You are allowed to flip a card such that the number which was previously on the top now comes at the bottom and vice versa.

Find the minimum flips that need to be performed to make all the numbers equal on either the top sides or the bottom sides. If it is impossible to make all the cards the same on either side then return ‘-1’.

For Example : 
If N = 4 and the numbers on the top sides are: { 1, 2, 3, 2 } and the numbers on the bottom sides are: { 2, 4, 2, 2}

Then the minimum number of flips required is equal to 1.
We can flip the 2nd card, the top sides now become: { 1, 4, 3, 2 } and the bottom sides are: { 2, 2, 2, 2}. This results in getting the same numbers on the bottom side.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of cards.

The second line of each test case contains the N integers ‘Top[i]’ denoting the number on the top side of the ith card.

The third line of each test case contains the N integers ‘Bottom[i]’ denoting the number on the bottom side of the ith card.
Output Format : 
For each test case, print a single integer denoting the minimum number of flips required.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10      
1 <= N <= 200
1 <= Bottom[i], Top[i] <= 10

Time limit: 1 sec
Sample Input 1 :
2
4
1 2 3 2
2 4 2 2
1
3
3
Sample Output 1 :
1
0
Explanation For Sample Input 1 :
For test case 1 : 
We will return 2, because:
We can flip the 2nd card, the top sides now become: { 1, 4, 3, 2 } and the bottom sides are: { 2, 2, 2, 2}. This results in getting the same numbers on the bottom side.

For test case 2 : 
We will return 0, because:
There is only one card, resulting in the top side of all the cards having the same numbers, so no flips are required.
Sample Input 2 :
2
4
9 8 9 8
8 9 8 9
2
5 10
9 8
Sample Output 2 :
2
-1
Hint

Can we check if it is possible to make all the numbers on one side equal to a number between ‘1’ to ‘10’?

Do we actually need to check for all the values between ‘1’ to ‘10’? Checking just for the numbers on the top and bottom side of the first card will be sufficient?

Approaches (1)
Greedy

We can simply find the number of flips required to make all the numbers on the top sides of the cards equal to ‘i’ where ‘i’ can range from ‘1’ to ‘10’. We can repeat the same thing for the bottom side, and finally, return the minimum number of flips out of them.


But note that for all cards to have the same value on either of the sides, the value should be either equal to the number on the top or on the bottom side of the first card. 


The steps are as follows :

  • Initialize “ans” to INT_MAX, it will store the minimum number of flips required.
  • Run a for loop for variable “target” from 1 to 10.
  • We will reduce the run time by pruning the search only when the value of “target” is equal to the top or the bottom number on the first card.
  • To check if the top sides can be made equal to “target”, initialize “cur” equal to 0, and iterate each card, if the top side is equal to target then move to the next card, else if the bottom side is equal to the target then increment the value of “cur” by one if both the top and the bottom side is not equal to the target value then its not possible to get this number on either side.
  • Repeat the same steps for the bottom side, and after each iteration update the value of “ans” if needed.
  • Finally, check if “ans” is equal to INT_MAX then return “-1” else return the value stores in “ans”.
Time Complexity

O( N ), where N denotes the number of cards


We iterate through each card a maximum of four times in the worst case.

Hence the time complexity is O( N ).

Space Complexity

O( 1 )


Extra space is not used. Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Minimum Card Flips
Full screen
Console