Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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]

Solution

Method 1 – Naive Simulation

Intuition

Simulate the process exactly as described: for each bulb, if it is off, press its switch, which toggles it and all bulbs to its right. This brute-force approach checks every bulb and updates the state array each time.

Approach

  1. Start with the given array of bulb states.
  2. For each bulb from left to right:
    • If the bulb is off (0), increment the switch press count.
    • Toggle the state of this bulb and all bulbs to its right (flip 0 to 1 and 1 to 0).
  3. Continue until all bulbs are on.
  4. Return the total number of switch presses.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
	int bulbs(vector<int>& A) {
		int n = A.size(), ans = 0;
		vector<int> state = A;
		for (int i = 0; i < n; ++i) {
			if (state[i] == 0) {
				++ans;
				for (int j = i; j < n; ++j) state[j] = 1 - state[j];
			}
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func bulbs(A []int) int {
	n := len(A)
	ans := 0
	state := make([]int, n)
	copy(state, A)
	for i := 0; i < n; i++ {
		if state[i] == 0 {
			ans++
			for j := i; j < n; j++ {
				state[j] = 1 - state[j]
			}
		}
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public class Solution {
	public int bulbs(int[] A) {
		int n = A.length, ans = 0;
		int[] state = A.clone();
		for (int i = 0; i < n; i++) {
			if (state[i] == 0) {
				ans++;
				for (int j = i; j < n; j++) {
					state[j] = 1 - state[j];
				}
			}
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	fun bulbs(A: IntArray): Int {
		val n = A.size
		var ans = 0
		val state = A.copyOf()
		for (i in 0 until n) {
			if (state[i] == 0) {
				ans++
				for (j in i until n) state[j] = 1 - state[j]
			}
		}
		return ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def bulbs(self, A: list[int]) -> int:
		n = len(A)
		ans = 0
		state = A[:]
		for i in range(n):
			if state[i] == 0:
				ans += 1
				for j in range(i, n):
					state[j] = 1 - state[j]
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
	pub fn bulbs(A: Vec<i32>) -> i32 {
		let n = A.len();
		let mut ans = 0;
		let mut state = A.clone();
		for i in 0..n {
			if state[i] == 0 {
				ans += 1;
				for j in i..n {
					state[j] = 1 - state[j];
				}
			}
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	bulbs(A: number[]): number {
		const n = A.length;
		let ans = 0;
		const state = A.slice();
		for (let i = 0; i < n; ++i) {
			if (state[i] === 0) {
				ans++;
				for (let j = i; j < n; ++j) {
					state[j] = 1 - state[j];
				}
			}
		}
		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n^2), because for each off bulb, we may flip up to n bulbs to the right.
  • 🧺 Space complexity: O(n), for the copy of the bulbs’ state.

Method 2 – Greedy Flip Count

Intuition

Instead of simulating every flip, we can track the number of flips so far. Each flip inverts the meaning of the bulbs to the right. If the current bulb’s state, after accounting for the number of flips so far, is off, we need to flip at this position. This way, we only count the minimum necessary flips.

Approach

  1. Initialize a counter for the number of flips performed so far.
  2. Iterate through the bulbs from left to right.
  3. For each bulb, if the current state (after accounting for flips) is off, increment the answer and the flip counter.
  4. Return the total number of flips needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
	int bulbs(vector<int>& A) {
		int ans = 0, flip = 0, n = A.size();
		for (int i = 0; i < n; ++i) {
			if ((A[i] ^ (flip & 1)) == 0) {
				++ans;
				++flip;
			}
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func bulbs(A []int) int {
	n := len(A)
	ans, flip := 0, 0
	for i := 0; i < n; i++ {
		if (A[i]^flip)&1 == 0 {
			ans++
			flip++
		}
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public class Solution {
	public int bulbs(int[] A) {
		int ans = 0, flip = 0, n = A.length;
		for (int i = 0; i < n; i++) {
			if ((A[i] ^ (flip & 1)) == 0) {
				ans++;
				flip++;
			}
		}
		return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun bulbs(A: IntArray): Int {
		var ans = 0
		var flip = 0
		for (i in A.indices) {
			if ((A[i] xor (flip and 1)) == 0) {
				ans++
				flip++
			}
		}
		return ans
	}
}
1
2
3
4
5
6
7
8
9

class Solution:
	def bulbs(self, A: list[int]) -> int:
		ans = 0
		flip = 0
		for a in A:
			if (a ^ (flip & 1)) == 0:
				ans += 1
				flip += 1
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
	pub fn bulbs(A: Vec<i32>) -> i32 {
		let mut ans = 0;
		let mut flip = 0;
		for &a in &A {
			if (a ^ (flip & 1)) == 0 {
				ans += 1;
				flip += 1;
			}
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
	bulbs(A: number[]): number {
		let ans = 0, flip = 0;
		for (const a of A) {
			if ((a ^ (flip & 1)) === 0) {
				ans++;
				flip++;
			}
		}
		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of bulbs.
  • 🧺 Space complexity: O(1), as we use only a few variables.