FInd the minimum number of switches to turn on all bulbs

returns the number of moments for which every turned on bulb shines codility
there are n bulbs numbered from 1 to n arranged in a row. the first bulb is plugged
glowing bulb problem solution
you are given a row of n bulbs numbered from 1 to n
kth glowing bulb solution
kth glowing bulb in c++
the bulb switcher
during a party harry wants to light up n bulbs

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.

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.

Count minimum right flips to set all values in an array, Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. "0 represents the bulb is off and 1 represents� 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.

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;

Faulty wiring and Bulbs | Practice, 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. 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.

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;

Bulbs, 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� 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]

Another way to understand the solution is grouping, Suppose we have [0,0,0] one switch can off or one all three of them, so we will try to find such groups. If first bulb is on we will not flip it. For example,

1 0 1 0 0 0 1 1 0 0

There are 3 groups of zeros(bulb OFF) here and 3 groups of one(bulb ON). But for the first 1 (ON bulb) we don't have to care about.So overall group of one = 2 and group of zeros = 3 and hence we will be needed 5 switches to turn on all bulbs.

int Solution::bulbs(vector<int> &A) {
    int group_one = 0;
    int group_zero = 0;

    if (A.size() == 0) return 0;

    if (A[0]) group_one++;
    else group_zero++;

    for (int i = 1; i < A.size(); i++) {
       if (A[i] == 0 && A[i - 1] == 1) group_zero++;
       else if (A[i] && A[i-1] == 0) group_one++;
    }
    // For All bulbs are either ON or OFF
    if (group_one && group_zero == 0) return 0;
    if (group_zero && group_one == 0) return 1;

    if (A[0]) group_one -= 1;

    return group_one + group_zero; }

Given an initial state of all bulbs, find the minimum number of , Each bulb has a switch associated with it, however due to faulty wiring, state of all bulbs, find the minimum number of switches you have to press to turn on all� Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. "0 represents the bulb is off and 1 represents the bulb is on." Input: The first line of input contains an integer T denoting the number of test cases.Each test case consists of number of bulbs N and the next line consist of the space separated state of N bulbs.

AliAMQ/NumberOfSwitches: N light bulbs are connected by , 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. The number of light bulbs and switches are limited to 1000. Example: If there are 10 light bulbs and 3 switches that toggle the bulbs in the range 1 to 7, 6 to 7, 6 to 10, then we can use all of the switches exactly once, and turn all the light bulbs from 1 to 10 on.

Light bulb invert � GitHub, You first turn on all the bulbs. On the third round, you toggle every third bulb ( turning on if it's off or turning off if Find how many bulbs are on after n rounds. All the cases are Obvious except the 4th. For the 4th you will require minimum 2 toggles to turn all the bulbs ON. (solution is to toggle the first and the last bulb).

Bulb Switcher, I can simultaneously flip all the bulbs from ON to OFF and vice versa in any submatrix. I need to switch OFF all the bulbs in a minimum number of moves and tell� Perhaps, you have 5 lights in the kitchen and you want to turn them on all at once. Smart switches are perfect for these situations where you want to turn off multiple lights on and off, at the same time. The second reason is because smart bulbs are not meant to be turned on and off constantly by a switch. Smart Bulbs always need to be on

Comments
  • Please include a text description of a concise image describing the problem.
  • Actually flipping the state of all the bulbs would be quite expensive. Instead, we just pretend that the bulbs' states are flipped. If a pretend bulb is off the real bulb is on, and vice versa. And if we want to pretend to flip a bunch of pretend bulbs, we end up pretending to pretend, which brings us back to reality. state records if we are pretending or not.
  • 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 ?
  • @user1846749: Far too long since you asked this, but I have clarified it in a separate answer on the same question.
  • You explained it in the most simplest way possible. Logically more connected to the way we are supposed to approach in practice
  • 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.
  • @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. :)