Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)

Read the question here from GCJ Qualification Round 2010:
» Problem A: Snapper Chain

Once you understand how the snapper works, it is easy. This problem can be solved in various ways, but the main observations are:

Let k be the number of times you snap your finger, n be the light’s position, and assume 0 = OFF and 1 = ON.

The configuration of the first five snappers (with the first snapper on the far left side) as k increases are:
00000 k = 0
10000 k = 1
01000 k = 2
11000 k = 3
00100 k = 4
10100 k = 5
01100 k = 6
11100 k = 7
00010 k = 8

See the pattern? The configuration of the snapper for any k is the binary representation of k itself!

For example, when k=3 and n=3, we know that the light is OFF because the snapper is in the OFF position (because the 3rd bit of k=3 is 0). When k=3 and n=2, the light is ON. However, when k=5 and n=3, the light is OFF even though the 3rd bit is 1. As the 2nd bit is 0, the electric couldn’t “flow” to the light bulb.

Therefore, in order for a bulb to light, it requires all of the bits from 1 to n to be all 1s.

The problem can still be solved using arrays representing the bits and iterate through them to check, but it is more efficient using bit manipulation. If you are familiar with bit manipulation, you can check if the bits from 1 to n are all 1s using the XOR operation and some bit shifting. My solution is shown below. This is just one sample solution. If you have a more elegant solution, you are welcome to add to that in the comments section.

VN:F [1.9.22_1171]
Rating: 3.3/5 (4 votes cast)
Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010), 3.3 out of 5 based on 4 ratings

17 thoughts on “Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)

  1. Anonymous

    This site is fantastic. Thank you very much.

    Here's an approach that may be a bit simpler, but I might have overlooked something because I'm not using XOR at all.

    if( ( ((1<<n)-1) & k ) == ((1<<n)-1) ){

    }

    VA:F [1.9.22_1171]
    +1
  2. ripper234

    You can solve this in O(1):

    boolean isPowered(int n, int k) {
    return k % (1<<n) == (1<<n) – 1;
    }

    Slightly simpler.

    VA:F [1.9.22_1171]
    +1
  3. aimless

    @1337:

    why this can’t work?

    k & ((1<<(n+1))-1) == ((1<<(n+1))-1)

    as all it needs is to find if k==pow(2,n)-1

    VA:F [1.9.22_1171]
    0
  4. Sonali

    Will the following also be a solution ?

    the above function will return the no of snaps required for a particular value of n. If it is the same as k then Snapper Chain is ON else OFF.

    VA:F [1.9.22_1171]
    0
  5. ashish anand

    can pleae anyone explain the logic of (((1 << (n-1)) ^ (k & ((1 << n)-1))) == ((1 << (n-1))-1)) in the above solution

    VA:F [1.9.22_1171]
    0
  6. Nanshu

    VA:F [1.9.22_1171]
    0
    1. Nanshu

      sorry, should invert the direction:

      VA:F [1.9.22_1171]
      0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*