Total Card Flip

Kader has a set of 64 cards: for each x between 0 and 63, he has a card that is blank on one side and has 2^x dots on the other side. Kader’s cards are placed on a table. At any moment, the cards show some integer between 0 and (2^64)-1, inclusive. To read the number, you just count all the dots you see. Kader is using the cards to count from A to B. That is, he is flipping some of the cards in such a way that the numbers A, A+1, …, B appear in this order.Kader is using the shortest possible sequence of flips. Additionally, he always flips the cards one at a time. Sometimes, changing the number from some Z to Z+1 requires Kader to flip more than one card. In that case, he flips the necessary cards ordered by the number of dots they have, starting with the one with the most dots.For example, if A=6 and B=8, the following will happen:

In the beginning, the card with 4 dots and the card with 2 dots are showing the dots, all other cards are blank side up. This shows the number 6.

He flips the card with 1 dot. Now the number 7 is shown. He flips the card with 8 dots. He flips the card with 4 dots. He flips the card with 2 dots. He flips the card with 1 dot. Now the number 8 is shown and he is done.

Given are longs A and B. Your method must return the largest number that will be shown at any moment during his counting.

Method: public long largestNumber(long A, long B)

Examples

1)i/p = 6 6 o/p = 3

Steps are
0110 = 6
0110 = 6
—————-
0110 = 6

2)i/p = 6 7 o/p = 7
Steps are
0110 = 6
0111 = 7
—————-
0111 = 7

3)i/p = 6 8 o/p = 15

Steps are
0110 = 6
1000 = 8
—————-
1111 = 15

4)i/p = 1 11 o/p = 15

Steps are
0001 = 1
1011 = 11
—————-
1111 = 15

5)i/p = 35 38 o/p = 39

Steps are
100011 = 35
100110 = 38
—————-
100111 = 39

import java.util.*;
import java.math.BigInteger;

public class BinaryCards {
    public long largestNumber(long A, long B) {
        if (A == B) return B;
        String AN = Long.toBinaryString(A);
        String BN = Long.toBinaryString(B);
        while (AN.length() != BN.length()) AN = '0' + AN;
        String ABN="";
        int i=0;
        for (; i<AN.length(); ++i) {
            if (AN.charAt(i)!=BN.charAt(i)) break;
            ABN+=AN.charAt(i);
        }

        for (; i<AN.length(); ++i)
            ABN+="1";
        System.out.println(AN + " - " + BN);
        return Long.valueOf(String.valueOf(ABN), 2);

    }

    public static void main(String[] args) {
        BinaryCards bc = new BinaryCards();
        System.out.println(bc.largestNumber(35,38));
        System.out.println(bc.largestNumber(1125899906842630L,1125899906842632L));
        //1125899906842639
    }
}
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: