Welcome to Subscribe On Youtube

3842. Toggle Light Bulbs

Description

You are given an array bulbs of integers between 1 and 100.

There are 100 light bulbs numbered from 1 to 100. All of them are switched off initially.

For each element bulbs[i] in the array bulbs:

  • If the bulbs[i]th light bulb is currently off, switch it on.
  • Otherwise, switch it off.

Return the list of integers denoting the light bulbs that are on in the end, sorted in ascending order. If no bulb is on, return an empty list.

 

Example 1:

Input: bulbs = [10,30,20,10]

Output: [20,30]

Explanation:

  • The bulbs[0] = 10th light bulb is currently off. We switch it on.
  • The bulbs[1] = 30th light bulb is currently off. We switch it on.
  • The bulbs[2] = 20th light bulb is currently off. We switch it on.
  • The bulbs[3] = 10th light bulb is currently on. We switch it off.
  • In the end, the 20th and the 30th light bulbs are on.

Example 2:

Input: bulbs = [100,100]

Output: []

Explanation:

  • The bulbs[0] = 100th light bulb is currently off. We switch it on.
  • The bulbs[1] = 100th light bulb is currently on. We switch it off.
  • In the end, no light bulb is on.

 

Constraints:

  • 1 <= bulbs.length <= 100
  • 1 <= bulbs[i] <= 100

Solutions

Solution 1: Simulation

We use an array $\textit{st}$ of length $101$ to record the state of each light bulb. Initially, all elements are $0$, indicating that all light bulbs are in the off state. For each element $\textit{bulbs}[i]$ in the array $\textit{bulbs}$, we toggle the value of $\textit{st}[\textit{bulbs}[i]]$ (i.e., $0$ becomes $1$, and $1$ becomes $0$). Finally, we traverse the $\textit{st}$ array, add the indices with a value of $1$ to the result list, and return the result.

The time complexity is $O(n)$, where $n$ is the length of the array $\textit{bulbs}$. The space complexity is $O(M)$, where $M$ is the maximum bulb number.

  • class Solution {
    public List<Integer> toggleLightBulbs(List<Integer> bulbs) {
        int[] st = new int[101];
        for (int x : bulbs) {
            st[x] ^= 1;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < st.length; ++i) {
            if (st[i] == 1) {
                ans.add(i);
            }
        }
        return ans;
    }
}


  • class Solution {
public:
    vector<int> toggleLightBulbs(vector<int>& bulbs) {
        vector<int> st(101, 0);
        for (int x : bulbs) {
            st[x] ^= 1;
        }
        vector<int> ans;
        for (int i = 0; i < 101; ++i) {
            if (st[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};


  • class Solution:
    def toggleLightBulbs(self, bulbs: list[int]) -> list[int]:
        st = [0] * 101
        for x in bulbs:
            st[x] ^= 1
        return [i for i, x in enumerate(st) if x]


  • func toggleLightBulbs(bulbs []int) []int {
	st := make([]int, 101)
	for _, x := range bulbs {
		st[x] ^= 1
	}
	ans := make([]int, 0)
	for i := 0; i < 101; i++ {
		if st[i] == 1 {
			ans = append(ans, i)
		}
	}
	return ans
}


  • function toggleLightBulbs(bulbs: number[]): number[] {
    const st: number[] = new Array(101).fill(0);
    for (const x of bulbs) {
        st[x] ^= 1;
    }
    const ans: number[] = [];
    for (let i = 0; i < 101; i++) {
        if (st[i] === 1) {
            ans.push(i);
        }
    }
    return ans;
}

All Problems

All Solutions