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.

1 2 3 4 5 6 7 8 9 10 11 |
int T, n, k; cin >> T; for (int i = 0; i < T; i++) { cin >> n >> k; cout << "Case #" << i + 1 << ": "; if (((1 << (n-1)) ^ (k & ((1 << n)-1))) == ((1 << (n-1))-1)) { cout << "ON\n"; } else { cout << "OFF\n"; } } |

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) ){

…

}

+1awsome

0You can solve this in O(1):

boolean isPowered(int n, int k) {

return k % (1<<n) == (1<<n) – 1;

}

Slightly simpler.

+1@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

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

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

0Will 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.

0via GCJ handle :neal.wu

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

-1int steps=(int)Math.pow(2, K)-1;

System.out.println(” Answer: “+((N+1)%(steps+1)==0&&(N+1)>=(steps+1)));

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

0The logic seems to be wrong. the right side should be just 1<<(n-1)

0int S(int n, int k)

{

return (k >> (n – 1)) & 1;

}

0`cout<<(k&(1<<n)==(1<<n))?"ON":"OFF";`

00sorry, should invert the direction:

0cout << (k+1)%(pow(2,n)) == 0 ? "ON" : "OFF";

0I have the same problem my friend i will fix now. Thank you so much this is perfect qualification.

0