# Duplication

Week of code 32 problem 1

#### PROBLEM STATEMENT

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[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 *zer*o. 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 *♥*