FInd the minimum number of switches to turn on all bulbs

Question

I am trying to understand the problem given here and its solution:

The problem states:

N light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. You can press the same switch multiple times.

Note : 0 represents the bulb is off and 1 represents the bulb is on.

Example:

Input : [0 1 0 1]
Return : 4

Explanation :

press switch 0 : [1 0 1 0]
press switch 1 : [1 1 0 1]
press switch 2 : [1 1 1 0]
press switch 3 : [1 1 1 1]

One of the answers given is:

int solve(int A[], int N) {

    int state= 0, ans = 0;
    for (int i = 0; i < N;i++) {
        if (A[i] == state) {
            ans++;
            state = 1 - state;
        }
    }

    return ans;
}

I can't seem to wrap my head around how the if statement does the correct thing.

Answer 1

Whenever we flip a switch we flip all the switches towards the right, so if we were searching for 0(off switch) now we need to search for 1(on switch) because we have flipped all the switches towards the right, lets look at an example : 0 1 1 0, now initially state = 0, when we encounter the first bulb we flip all the switches, i.e 1 0 0 1 but in the array the values are still 0 1 1 0, so we need to be able to recognize that the bulb at the second index is switched off due to the previous flip, so we change the state to 1 - state, which makes the state that we are looking for is 1, similarly flipping the switches changes the criteria of the next state that we will search.

I have written a code snippet below, that would be more understandable

bool flipped = false;
int ans = 0;
for(int i = 0;i < N;i++){
    if(flipped == false){
        if(A[i] == 0){
            ans++;
            flipped = true;
        }
    }else if(flipped == true){
        if(A[i] == 1){
            ans++;
            flipped = false;
        }
    }
}

Here i am using the flipped variable that tells whether the bulbs have been flipped or not if they have been flipped then we will search for 1(on switches), because in reality they are 0(off) because of previous flip.