FInd the minimum number of switches to turn on all bulbs

user_2857014 0
Viewed 21670

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.

bit-manipulation algorithm java
5 Answers

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;
user_18357690

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;
user_122126810

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; }
user_45207950

A much simpler approach to the problem.

int solve(int A[], int N) {
    // Initially no switches have been flipped
    boolean isFlipped = false;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        // Case 1: If the array element is 0 and switches have not been flipped 
        // then it needs to be flipped to turn on the switch.
        // Case 2: If the array element is 1 and switches have been flipped 
        // then it means this value is actually 0 and hence it needs to be 
        // flipped again to turn on the switch.
        if ((A[i] == 0 && !isFlipped) || (A[i] == 1 && isFlipped)) {
            ans++;
            isFlipped = !isFlipped;
        }
    }
    return ans;
}
user_48953460
Related