There are only two sequences that evolve to become the zero sequence: the zero sequence itself (trivially) and the sequence 1010101....101, ie. alternating ones and zeros that begins and ends with a one. Try to prove this formally.

Using the answer for question 1, we see that an even length sequence will only ever evolve to the zero sequence if it is already the zero sequence. ie. an even length sequence with at least one nonzero element will never become the zero sequence.

If we denote by A[n][i] the value of the i'th element on step n, we can find the two step recurrence by substituting the original recurrence into itself. The one-step recurrence can be written as

A[n+1][i] = A[n][i-1] ^ A[n][i+1]

and hence the two step recurrence reads

A[n+2][i] = A[n+1][i-1] ^ A[n+1][i+1]
          = (A[n][i-2] ^ A[n][i]) ^ (A[n][i] ^ A[n][i+2])
          = A[n][i-2] ^ A[n][i+2]

where we have used the fact that A[n][i] ^ A[n][i] cancels out.

The key observation that we have to make is that the values of the sequence every two steps at the even positions i depends only on the elements at the other even positions i-2, i+2, ie. the even and odds can be treated independently!

The fact that we noticed that the even and odd positions are independent on every two-step suggests a divide-and-conquer approach in which we split the sequence into even and odds and solve recursively. First, we have several base cases:

• If the sequence contains all zeros, the answer is clearly YES.
• If the sequence has an even length, the answer is NO (observation from question 2.)
• If the sequence contains only one element, the answer is YES.

From here, we have an odd length sequence of length at least three that is not all zeros. We first consider the subsequence of elements at even positions only. If this subsequence is a NO, then clearly the entire sequence is a NO. If this subsequence is a YES, then we know that at some point, at every even step, the original sequence will contain all zeros in the even positions. This is almost enough to tell us that the sequence becomes all zeros, but not quite, since we still do not know what happens on the odd steps. So, we can simulate just one step of the process, and repeat the exact same logic to determine whether the even elements evolve to zero on the odd steps too.

If we find that the even position elements eventually evolve to zero on both the odd and even steps, then we deduce that at some point, the even position elements remain fixed at zero forever. It is then easy to see that at this point, the entire sequence must become zero. If not, then we know that there must always be a zero somewhere in the sequence.

Hence, the answer can be determined recursively by extracting the subsequence of the even position elements, simulating one step and extracting even position elements again, and solving the subproblems for the smaller subsequences, returning YES if and only if both the even position elements at the current step and next step both returned YES.

Since every level of recursion solves a problem half the size of the original, there will be O(log(n)) levels of recursion, taking O(n) time each. Therefore the running time of the algorithm is O(n log(n))

A simple, recursive implementation of the divide-and-conquer solution above in C++ is:

// Returns true if the sequence eventually becomes all zeros
bool dies(const string& bitverse) {
	int n = (int)bitverse.size();
	if (count(bitverse.begin(), bitverse.end(), '1') == 0) return true;
	if (n % 2 == 0) return false;
	if (n == 1) return true;
	string current, nxt;
	for (int i = 1; i < n - 1; i += 2) {
		current += bitverse[i];
		nxt += (bitverse[i-1] == bitverse[i+1]) ? '0' : '1';
	}
	return dies(current) && dies(nxt);
}