Week of code 32 problem 1
We have a binary string S . 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 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
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=S=S=1
Hey!,but S is not actually s right. Yeah,but we read out S to write S. This will get cleared when we take S of length 16. S=0110100110010110
Now lets calculate for index i=14. S=S=S=S=0. woah! but S is 1 not zero. But we can say for certain that we got S from S. Looking closer you can notice that whenever there was an odd number of transition to reach either S/S we need invert the value at S/S. 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.
Hope this helped :) ……if it did give a ♥