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 !

Can you post the link to question?

You can ask me if something not clear in question description.

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.

Hi , i have provided the link . The question is slightly different from the link given (since that question can be solved by brute force)

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

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.

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

Where is the 1st index?

Initial string is 10000... . S[0]=1 , S[i]=0 , i > 0 .

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.

Thanks very nice observation

SpoilerIt'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)$$$.

can u give code for this

[deleted, my approach was incorrect]

if on day 12 string is

`111100001111`

then on day 13 string should be`100010001000`

but according to this, it will be`10101010101`

I think we have to do a simultaneous update on the string

Am I missing something?

Yes you are correct, i made a mistake in constructing the sequence.

Will edit my comment. Thanks for pointing that out!