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.
Where is the 1st index?
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.
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)$$$.
[deleted, my approach was incorrect]
if on day 12 string is
111100001111then on day 13 string should be100010001000but according to this, it will be10101010101I 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!