### supersonic11's blog

By supersonic11, 6 weeks ago,

Given an binary string 100000... of size '$m$' on day 0 , For each subsequent day, the updated value at each index >= 1 is given by xor of the value of (i-1)th index and ith index on the previous day . Print the binary string on nth day . where $1<=n,m<=1e5$ .

I am able to see some pattern after writing down the string for several days but not able to make it concise .

Edit : Following is the link

Read the first question of coding round.

question is slightly different from the link given (since that question can be solved by brute force)

I asked this question and my contribution went from 0 to -15 . I agree that i am not helping someone but i thought people might find this problem interesting and i can get help . Also i tried for few hours before posting . Even small help from your side will motivate me to grow and work harder .

So many nice ideas provided . I want every one in comment section THANK YOU for helping !

• -11

 » 6 weeks ago, # |   0 Can you post the link to question?
•  » » 6 weeks ago, # ^ |   -13 You can ask me if something not clear in question description.
•  » » » 6 weeks ago, # ^ |   +21 Can you post the link? Generally, without posting a link to the source, people will suspect this is from an in-progress contest or interview.
•  » » » » 6 weeks ago, # ^ |   0 Hi , i have provided the link . The question is slightly different from the link given (since that question can be solved by brute force)
•  » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 What is the length of the bitstring? try doing brute force to exploit the pattern here's what i think :find i such that bit(i)==1 let ans[n] be the answer array or bitstring. Then a[0],a[1],...a[i] will all remail same for any n.bit(i+k) will remain zero for k days and change depending on the bit(i+k-1). For example bit(i) is set. then bit(i+1) flip everyday. bit(i+2) will flip after 2 days. Except (i+1) and (i+2) bit(i+3) will stay zero for 3 days and turn 1 and then back to 3 days zero and so on You just have to worry about when will the flipping start based on previous bits flipping.P.S : I am still a noob in programming this is my thought process and i may very likely be wrong so i suggest you verify and then consider.Thank you
•  » » » » 6 weeks ago, # ^ |   0 i have provide both link and more details . If i understood your solution correctly then are you are telling some diagonal pattern ? Can you please explain with help of an example.
•  » » » » » 6 weeks ago, # ^ |   0 I had messed that observation sorry about that.Answer for n=16 is (printed as b31,b30,...,b0)0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
 » 6 weeks ago, # |   0 Where is the 1st index?
•  » » 6 weeks ago, # ^ |   0 Initial string is 10000... . S[0]=1 , S[i]=0 , i > 0 .
 » 6 weeks ago, # | ← Rev. 2 →   0 P.S. I'm sorry. The statements I posted are completely wrong.
 » 6 weeks ago, # | ← Rev. 2 →   +8 The binary string (0 based indexing) would be constructed as the following : If the index is a submask of n, the character would be of value '1' If not, it would be '0' A number $X$ is a submask of another number $Y$ iff $X \ AND \ Y = X$I am not sure exactly how to explain how I got this, however, since I randomly tested weird ideas. Specifically, I tested writing out the strings, then saw it has a "recursive" pattern with a similar shape to Sierpinski's Triangle, and has a "binary"-ish pattern to it.
•  » » 6 weeks ago, # ^ |   0 Thanks very nice observation
 » 6 weeks ago, # |   +9 Spoiler1000000000000000 1100000000000000 1010000000000000 1111000000000000 1000100000000000 1100110000000000 1010101000000000 1111111100000000 1000000010000000 1100000011000000 1010000010100000 1111000011110000 1000100010001000 1100110011001100 1010101010101010 1111111111111111 It's clear by inspection of the first few iterations of this process that they form a finite Sierpiński triangle-like structure. If you're familiar with this then Lucas's theorem may come to mind. If not, you might notice that on some days the string contains only two ones, and that this happens on days 1, 2, 4, 8, 16, ..., $2^k$. It's then easy enough to prove by induction that the string on day $d + 2^k$ is equal to the xor of the string on day $d$ with its $2^k$-th shift. With that observation in hand, it is easy enough to write an $O(m \log n)$ solution using the binary representation of $n$ and bitsets, and not very much harder to optimize this to $O(m)$.
•  » » 5 weeks ago, # ^ |   0 can u give code for this
 » 6 weeks ago, # | ← Rev. 2 →   -8 [deleted, my approach was incorrect]
•  » » 6 weeks ago, # ^ |   +8 if on day 12 string is 111100001111 then on day 13 string should be 100010001000 but according to this, it will be 10101010101I think we have to do a simultaneous update on the stringAm I missing something?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes you are correct, i made a mistake in constructing the sequence.Will edit my comment. Thanks for pointing that out!