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

May 8, 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: 0.0/5 (0 votes cast)

### 12 responses to Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)

1. 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]
0
2. 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]
0
3. @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. ((k&((1<<n)-1)) == ((1<<n)-1))

VA:F [1.9.22_1171]
0
5. k & ( (1 << (n-1) ) – 1 ) == ( (1 << (n-1) ) – 1)

VA:F [1.9.22_1171]
0
6. 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
7. via GCJ handle :neal.wu

return (k+1)%(1<<n) == 0 ? ON : OFF

VN:F [1.9.22_1171]
0
8. int steps=(int)Math.pow(2, K)-1;

VA:F [1.9.22_1171]
0
9. 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
• The logic seems to be wrong. the right side should be just 1<<(n-1)

VA:F [1.9.22_1171]
0
10. int S(int n, int k)
{
return (k >> (n – 1)) & 1;
}

VN:F [1.9.22_1171]
0