Find number of 1s after x number of operations

Revision en1, by rs0, 2021-05-24 12:18:09

Hi All, I am not sure whether it is the right place to post this question or not. But I am doing it anyway. I came across the following problem in an online assessment recently for a company. I could come up with a brute force solution, but could not find any decent solution for the given problem. Any help (hints, concept names, algorithm hint) will be a great help.

You are given an array V of N integers having values either 0 or 1. After one operation, the values of all array elements get updated and becomes 1 if both of their neighbours have equal values previously, 0 otherwise. The elements on the first and last index of the array get updated to 0 after every operation Note: The values don't get updated during operation which means that all values get updated based on previous values of V. The only constraint that I could remember was V can have upto 10^5 elements

Ex: ~~~~~ Input: V = [0,1,0,1] X = 2 Output: 0 ~~~~~

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rs0 2021-05-24 16:31:25 2 Tiny change: '\n\nEx: \n~~~~~\nI' -> '\n\nEx: \n\n~~~~~\nI'
en2 English rs0 2021-05-24 12:18:39 0 (published)
en1 English rs0 2021-05-24 12:18:09 1001 Initial revision (saved to drafts)