An interesting logic problem?

Question

Programming

Yesterday at work, a colleague asked a programming riddle. I am still thinking about her solution.
Given some closed array of numbers (circle for simplicity) filled with zeros and ones in random order. The length is N.
As soon as changing the elements to 0 and 1 and sorting through them one by one, you can find N.

Answer 1

It seems to me that the solution can be further simplified:
0. remember the current value. let's say zero.
1. We go to the right, counting the steps until we reach zero, while we have passed A steps
2. We put one instead of zero
3. We go A steps to the left (to the original)
4. If there is 1 (the value has changed) then N=A, if there 0 then we go to point 1.
In theory, it should be half as long, because you need to return to the starting point on average half as often.

Answer 2

The task is similar to a looped train of wagons, you need to count the number of wagons. And you can turn on / off the light in the cars (change to 0 and 1, respectively). Suppose we have a wagon (array point) in which we are currently located. Turn on the light in this car (1). We go to the next left car, turn off the light (0). We go to the next right car from the initial one, turn off the light (0). So, we have sequence 010. Again we go to the neighboring left car and turn on the light (1). We go to the neighboring right car and check: if the light is off (and we turned it on in the previous steps), then the number of cars is 2. If not, then the algorithm continues.
That is, each iteration can be described as follows:

011...110
<-
111...11x
->
if
111...111 мы нашли середину состава, можно посчитать количество вагонов
else (имеем 111...110)
do
111...111
0111...1110.
repeat

Answer 3

The question is how much memory we have - can we remember the number N. Otherwise, they will give you an array of length 2 ^ 2 ^ 64 ...
It would be interesting to write a program for a Turing machine that turns off the lights in the entire train.

Answer 4

If we simplify, then:
1. We put on cell 1.
2. A:=1
3. A:=A*2
4. We take A steps to the right, after each step we write in cell 0.
5. We take A steps to the left.
6. If in cell 1, go to item 3.
7. Put in cell 1 and go to the right, counting steps until we find 1. The
maximum number of steps is N * 9-12 (for N> 1)

Answer 5

And what is the goal, to determine N in the minimum number of steps? Please clarify, can I remember the states of the elements that I set?

Answer 6

By the way, “switching through them one at a time” can be understood as “moving only to the right.” In this case, as far as I understand, the problem is unsolvable.