Problem A: Snapper Chain Solution (Google Code Jam Qualification Round 2010)
May 8, 2010 in bit operations
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"; } } |
Anonymous said on February 2, 2011
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) ){
…
}
Ivan said on March 27, 2013
awsome
ripper234 said on February 15, 2011
You can solve this in O(1):
boolean isPowered(int n, int k) {
return k % (1<<n) == (1<<n) – 1;
}
Slightly simpler.
aimless said on May 13, 2011
@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
xyyang said on July 17, 2011
((k&((1<<n)-1)) == ((1<<n)-1))
Bala said on July 24, 2011
k & ( (1 << (n-1) ) – 1 ) == ( (1 << (n-1) ) – 1)
Sonali said on November 7, 2011
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.
Karthikeyan.M said on June 13, 2012
via GCJ handle :neal.wu
return (k+1)%(1<<n) == 0 ? ON : OFF
vincent said on November 19, 2012
int steps=(int)Math.pow(2, K)-1;
System.out.println(” Answer: “+((N+1)%(steps+1)==0&&(N+1)>=(steps+1)));
ashish anand said on November 25, 2012
can pleae anyone explain the logic of (((1 << (n-1)) ^ (k & ((1 << n)-1))) == ((1 << (n-1))-1)) in the above solution
zyfo2 said on January 11, 2013
The logic seems to be wrong. the right side should be just 1<<(n-1)
Yi Shan said on March 26, 2013
int S(int n, int k)
{
return (k >> (n – 1)) & 1;
}