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.

Solution 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.

Solution 2

There's just two points to understand:

1. Since the bulbs on the right are flipped on flipping a particular switch, it makes sense to iterate on the bulbs from left to right, i.e. index 0 to bulbs.length; and,

2. Because the state of the bulbs on the right can be inverted, we need to know whether to treat the bulb's state as inverted or treat it as it is.

---

Here's the short and sweet code to implement the above two points. Read the comments and it will be super simple to understand:

int count = 0;
boolean flip = false; //Initially we don't flip the states, so flip is false

for(int i = 0; i < bulb.length; i++) {
    //A bulb is ON when:
    //1. The bulb is ON and it is not supposed to be flipped.
    if (bulb[i] == 1 && !flip) continue;

    //2. The bulb is OFF but it is supposed to be flipped.
    if (bulb[i] == 0 && flip) continue;

    //Now the bulb is OFF, so we turn it ON i.e. increment count and
    //invert the flipping condition for the rest of the bulbs on the right.
    count++;
    flip = !flip;
}

return count;

Solution 3

Another easy solution:

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

    int count=0;
    for (int i = 0; i < N;i++) {
        if ((A[i] == 0 && count%2==0)|| (A[i]==1 && count%2==1)) {
            count++;
        }
    }
    return count;

Comments

[user1846749]

Why in this problem starting from left to right gives optimal solution , can it be starting to flip from some 1 in mid lead to better result ?

[displayName]

@user1846749: Far too long since you asked this, but I have clarified it in a separate answer on the same question.

[HalfWebDev]

You explained it in the most simplest way possible. Logically more connected to the way we are supposed to approach in practice

[HalfWebDev]

Following test cases help reach this solution faster. #1 [1, 1, 1, 1] if (bulb[i] == 1 && !flip) continue; statement can be formed from this. #2 [0, 1, 0, 1] or anything with zeros and 1 basically can help form the the part if (bulb[i] == 0 && flip) continue; and rest of the count update easily.

[displayName]

@kushalvm: This logical explanation is not a coincidence. I solved this problem while preparing for interviews. So at that time I was approaching every problem logically. It is a good habit to take as a programmer. The code we write with that habit is easier for other developers to understand too. :)