Mike_Mirzayanov_Is_Pussy's blog

How to solve following bitwise xor problem in O(n)
By Mike_Mirzayanov_Is_Pussy, 4 years ago, In English

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 !

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post the link to question?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the 1st index?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • P.S. I'm sorry. The statements I posted are completely wrong.
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Spoiler

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

[deleted, my approach was incorrect]

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      Will edit my comment. Thanks for pointing that out!

      → Reply