Recently, I’m in an interviewing cycle for a new job. For this I find a useful to bang my head out on problems such like the Google Code Jam. The first problem in this year’s practice round is called Snapper Chain.

Before reading further I do suggest you read the problem description first.

It took me a while to come up with the right answer. I actually started to code the algorithm first before realize the real solution. Below you can see my first attempt which might be a correct solution but it has a time complexity of O(K), where K is the number of times snapping the finger. It can go up to 10^8 times. When running the code below with the large problem set it would take forever to finish.

#include <algorithm> #include <cassert> #include <fstream> #include <iostream> #include <vector> using namespace std; enum snapper { no_power_off = 0 , no_power_on // = 1 , power_off // = 2 , power_on // = 3 }; bool is_powered( snapper s ) { return ( s > no_power_on ); } bool is_on( snapper s ) { return ( s == no_power_on || s == power_on ); } bool all_on( const vector< snapper >& chain ) { for( size_t i = 0; i < chain.size(); ++i ) { if( is_on( chain[i] ) == false || is_powered( chain[i] ) == false ) return false; } return true; } void snap( vector< snapper >& chain ) { // loop through all devices and toggle their state if they are powered for( size_t i = 0 ; i < chain.size(); ++i ) { if( is_powered( chain[i] )) { chain[i] = ( is_on( chain[i] )) ? power_off : power_on; } } // power of all snappers for( size_t i = 0 ; i < chain.size(); ++i ) { chain[i] = ( is_on( chain[i] )) ? no_power_on : no_power_off; } // first snapper is always powered chain[0] = ( is_on( chain[0] )) ? power_on : power_off; // loop through all snappers and turn on when possible // start with second snapper for( size_t i = 1 ; i < chain.size(); ++i ) { snapper& cur = chain[i]; snapper prev = chain[i-1]; if( is_powered( prev ) && is_on( prev ) ) { cur = ( is_on( cur )) ? power_on : power_off; } else { // no other snapper can be powered break; } } } bool run( int n, int k ) { vector< snapper > chain( n ); fill( chain.begin(), chain.end(), no_power_off ); chain[0] = power_off; for( int i = 0; i < k; ++i ) { snap( chain ); } return all_on( chain ); } int main(int argc, char* argv[]) { FILE* in; in = fopen( "../A-large-practice.in", "r" ); ofstream out( "../large_results.txt" ); if( in == NULL ) exit( 1 ); int tasks = 0, n = 0, k = 0; fscanf( in, "%d", &tasks ); for( int i = 1; i <= tasks; ++i ) { fscanf( in, "%d %d", &n, &k ); if( k == 0 ) { out << "Case #" << i << ": " << "OFF" << endl; } else { bool t = run( n, k ); out << "Case #" << i << ": " << ( ( t == true ) ? "ON" : "OFF" ) << endl; } } fclose( in ); return 0; }

Clearly there must be a better solution hopefully with O(n) time complexity, where n is the number of snappers. N is bound to be 30 or less.

While reading the problem description over and over again I noticed the last sample, n=4 and k=47. Apparently, the light is on for this case. Converting the number 47 into binary code make it “0010 1111”. Mhmm, n=4 and there are four ones in the first half byte. Could it be when the number first bits set to 1 equals the number of snapper that the light is on? Good thing I had the my code above to “prove” my theory. Indeed, I was right and my next solution only depended on the number of snappers.

The upper half byte ( “0010” ) here refers to the number the light goes on. The first time it goes on is when snapping 15 times (k=15). The next times are when snapping 31 and 47 times, respectively.

n=4

k=15 – 0000 1111

k=31 – 0001 1111

k=47 – 0010 1111

k=63 – 0011 1111

etc…

bool run( int n, int k ) { int binary_N = 1; for( int i = 0; i < n - 1 ; ++i ) { binary_N = binary_N << 1; binary_N = binary_N + 1; } if(( k & binary_N ) == binary_N ) { return true; } return false; } int main(int argc, char* argv[]) { FILE* in; in = fopen( "../A-large-practice.in", "r" ); ofstream out( "../large_results.txt" ); if( in == NULL ) exit( 1 ); int tasks = 0, n = 0, k = 0; fscanf( in, "%d", &tasks ); for( int i = 1; i <= tasks; ++i ) { fscanf( in, "%d %d", &n, &k ); if( k == 0 ) { out << "Case #" << i << ": " << "OFF" << endl; } else { bool t = run( n, k ); out << "Case #" << i << ": " << ( ( t == true ) ? "ON" : "OFF" ) << endl; } } fclose( in ); return 0; }

I have summited to my results to google and they are correct. Nice…

Until now I have not cheated nor taken a look at the provided analysis. Let’s see what the immortals came up with…

OK OK, after having read google’s analysis it’s more clear now why my solution is the right one. I’m not sure I get it completely but hopefully writing about will help me understanding.

With my own words the correct way of thinking here goes like this:

Take two binary numbers, p and q. p represents the on/off state of all snappers, whereas q represents the powered/unpowered state. Each number has as many bits as there are snappers. For now we assume it’s N=4.

The initial states are p = 0000 and q=0001. The first snapper ( read right to left ) is always powered. Now, two operations need to be accomplished for each snap.

1. Calculate the on/off situation for all snapper according to the last state. p_i = p_i-1 XOR q_i-1

2. After 1, update the powered/unpowered situation. q_i = foo( p_i ). The algorithm foo is going from right to left and determines if snapper at position i is powered based on the state of i-1. If snapper i-1 is ON and POWERED snapper i is powered as well.

Here a short run for n=4 and k=5

0: p0=0000 q0=0001

1: p1=0001 q1=0011 – the rightmost bit is both 1 for p_1 and q_0 meaning that the second snapper is powered.

2: p2=0010 q2=0001 – don’t forget to start with the rightmost bit and then make your way left

3: p3=0011 q3=0111

4: p4=0100 q4=0001

When p3 = 0011 the result for q3 is this: The snapper is always on.

q3 = 1

According to p3 the state of the first snapper is on. Now we know the second snapper is powered.

q3 = 11

Again, the second snapper is ON, too. See p3. above. Meaning the third snapper is powered.

q3 = 111

The third snapper is not in on state meaning we have determined q3 – 0111.

It’s easy to see that every p is p_i-1 + 1. p2 = p1 + 1.

The next step in understanding the solution is to realize that we can take a p and determine q from it’s bit pattern. For instance, take the the bit pattern p_i=10101111 then q_i must be q=00011111 since p_i+1 = p_i XOR q_i. p_i+1 MUST be p_i+1.

10101111 XOR 00011111 10110000

Here we can see the 5 rightmost bits in q are powered. Meaning if we only have 4 snappers they are all powered and though the light is.

Though, when N rightmost bits of K are 1 the light is ON.

Thanks for reading.