0

I have N playing cards on which numbers are written on front as well as back.Now In one move I can flip any card so that its bottom now becomes the top.

Given the numbers on top and bottom of cards I need to find minimum number of moves that can make at least half of the cards show same number on their top.

If it is not possible to do so then also tell that it is not possible.

Example : Say we have 3 cards and represented as (number on top,number on bottom)

Card 1 : (3,10)

Card 2 : (10,3)

Card 3 : (5,4)

Now ,here minmum moves is just 1 as we can flip the first card so that number on the top becomes 10. Since two of the three cards have same number on their top (10), we do not need to change anything else, so the answer is 1.

2
  • Is it possible that one card has the same number on both faces ?
    – hivert
    Feb 1, 2014 at 10:40
  • @hivert yeah ..they can be same Feb 1, 2014 at 11:52

3 Answers 3

1

The following point is not completely clear from your question:

  • I'm assuming that you have the complete information, ie that you know from the beginning what is on top an bottom of each card;

I'll go for the following:

  • let N = number of cards;
  • for each number i appearing on a card, count the number m(i) of cards where it appear (top or bottom);
  • if no m(i) is greater than N/2 then fail
  • for each number i appearing on a cord, count the number top(i) of cards where if appear on top;
  • compute c the number where m(c) - top(c) is minimum;
  • flip m(c) - top(c) such that c is on bottom but not on top.
2
  • aren't you assuming that the cards have different numbers on both sides? Feb 1, 2014 at 13:00
  • @Bartlomiej Lewandowski: no I'm not since I count the number of cards, not the number of faces. EG: in the second point, if it appear on both face, it counts only for one.
    – hivert
    Feb 1, 2014 at 14:19
0
  1. N be the number of cards.
  2. top(v) be the count how often v appears on top, v=0..N-1
  3. bottom(v) be the count how often v appears on bottom.
  4. Sort the values according to how often they appear on top, top(v)
  5. Pick the value v with the biggest top(v)
  6. If top(v)+bottom(v) >= N/2 that v is your result, otherwise pick the next one from the sorted list

Here is that algorithm in Python:

from collections import defaultdict
def cardflip( cards ):
    # 'tops' maps the value to the count of cards
    # showing that value on top
    tops = defaultdict(int)
    # 'bottoms' maps the value to the count of cards
    # showing that value on bottom
    bottoms = defaultdict(int)
    for c in cards:
        topvalue = c[0]
        tops[topvalue] += 1
        bottomvalue = c[1]
        if bottomvalue != topvalue:
            # if it's the same on both side we ignore the bottom
            bottoms[bottomvalue] += 1
            tops[bottomvalue] += 0 
    # topcounts is a list of pairs (value, count)
    topcounts = list(tops.items())
    # sort it by count, the biggest first
    topcounts.sort( key = lambda x : -x[1] )
    for (v, c) in topcounts:
        if (c + bottoms[v]) * 2 >= len(cards):
            final = v
            break
    else:
        print( "there is no result" )
        return

    print( "value=", final, "moves=", (len(cards)+1)//2 - tops[final] )


cardflip( [ (3,10), (10,3), (5,4) ] )
cardflip( [ (1,3), (2,3), (4, 5), (6, 7), (9,3), (11,2)] )

If you don't have Python available, you can try it here: http://ideone.com/J1qD6m , just press fork right above the source.

0

For a linear-time, constant-space algorithm: use an algorithm due to Misra and Gries to find the numbers that appear on at least one-quarter of the card sides. There are at most four such candidates; no other number can appear on at least half of the face-up cards. For each candidate, determine how many flips are necessary.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.