Duplication

Week of code 32 problem 1

PROBLEM STATEMENT

We have a binary string . At each step we append another binary string T. T is the 1’s complement of S (example: S=10 then T=01) .

step 1: S=10, T=01 ,new S=S+T =1001

step 2:S=1001, after appending S=10010110

step3:S=10010110,after appending S=1001011001101001

we keep doing this till length of S exceeds 1000. Now given Q queries,where each query is an index i of the string S . Print value at S[i] .Example(i=5,S[5] will be 1)

The constraints for this problem is very low. So we can simply write a program to generate the string of length > 1000 and store it in our submission program and answer queries in O(1) time. There’s no fun in that :p but its clever right!

THE ORIGINAL PROBLEM

This problem is actually a modified problem given in APAC(did they actually duplicate it ?). Just that this one is much easier. A good solution to the apac problem can be found HERE

THE SOLUTION

We notice that the string to be generated grows really fast (2^n) . So if we try to do this in paper its easy just read from index one and keep appending 0 if we read 1 and 1 if read a zero. So all the numbers in our string are coming from the first string S=01 . Now all we need to do is figure out how to map any index(i) in string(S) greater than 1(i>1 assuming zero indexing) to S=01.

Cool lets take S with length 4, S=0110

Now given index 3 we can map it to index 1since that’s were it came from . And index 2 to index 0.

Lets take S with length 8, S=01101001

Now given index 7. lets map it to S=0110 . That’ll be index 3. Now we know that 3 is mapped to index 1(remember zero indexing) . so S[7]=S[3]=S[1]=1

Hey!,but S[7] is not actually s[3] right. Yeah,but we read out S[3] to write S[7]. This will get cleared when we take S of length 16. S=0110100110010110

Now lets calculate for index i=14. S[14]=S[6]=S[2]=S[0]=0. woah! but S[14] is 1 not zero. But we can say for certain that we got S[14] from S[0]. Looking closer you can notice that whenever there was an odd number of transition to reach either S[0]/S[1] we need invert the value at S[0]/S[1]. If it is even then no inversion is required.

So what we are essentially doing here is finding a relative position of our current index if the length of the string S was smaller than our current size which is a power of 2(since length of S will always be a power of 2). We repeatedly do this till we reach either index 0/1. For which we know the answer , also we know the number of transitions made, therefore we can give a right answer.

TIME COMPLEXITY

O(log(n))

Hope this helped :) ……if it did give a