Clever Geek Handbook

Minimal card flipping

I have N playing cards with numbers written on both the front and back. Now, in one move, I can flip any card so that its bottom is now the top.

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

If this is not possible, then also inform that it is not possible.

Example: Suppose we have 3 cards and are presented as (number on top, number on bottom)

Card 1: (3,10)

Card 2: (10.3)

Card 3: (5.4)

Now, here minmum move is just 1, since we can flip the first card so that the number on the top becomes 10. Since two of the three cards have the same number on the top (10), we don't need to change anything otherwise, so the answer is 1.

0


source to share


3 answers


The next question is not entirely clear from your question:

  • I assume you have complete information i.e. from the very beginning you know what is at the top of the bottom of each card;


I'll go for the following:

  • let N = number of cards;
  • for each number i

    that appears on the card, count the number of the m(i)

    cards where it is displayed (top or bottom);
  • if m(i)

    more than N/2

    , then
  • for each number i

    that appears on the line, count the number of top(i)

    cards, if displayed at the top;
  • calculate the c

    number, where is the m(c) - top(c)

    minimum;
  • flip m(c) - top(c)

    such that c

    at the bottom, but not on top.
+1


source


  • N

    - the number of cards.
  • top(v)

    will count how often v appears from above, v=0..N-1

  • bottom(v)

    how often v appears at the bottom will be counted.
  • Sorting values ​​according to how often they appear at the top, top(v)

  • Select the value v

    with the largesttop(v)

  • If top(v)+bottom(v) >= N/2

    , what v

    is your result, otherwise select the next one from the sorted list

Here's the 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 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, you can try it here: http://ideone.com/J1qD6m , just hit the fork button right above the source.

0


source


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

0


source






More articles:


All Articles