Bulb Switcher IV | LeetCode Problems And Solution

This post explains the LeetCode problem Bulb Switcher IV step by step: the problem statement, input and output format, constraints, a sample test case and a working solution in Java and Python that you can study and run.

Difficulty:Medium

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is '1' if the i-th bulb is turned on and is '0' if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:
Choose any bulb (index i) of your current configuration.

Flip each bulb from index i to n-1.
When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3

Input: target = "00000"
Output: 0

Example 4

Input: target = "001011101"
Output: 5

Constraints

1 <= target.length <= 10^5

target[i] == '0' or target[i] == '1'

Bulb Switcher IV Solution in Java

class Solution {
public:
    int minFlips(string s) {
        int n = s.size(), L = 0;
        for (; L < n && s[L] == '0'; ++L);
        if (L == n) return 0;
        int ret = 0;
        for (int i = L, j; i < n; i = j) {
            for (j = i + 1; j < n && s[j] == s[i]; ++j);
            ++ret;
        }
        return ret;
    }
};

Bulb Switcher IV Solution in Python

class Solution(object):
    def minFlips(self, target):
        flip = ans = 0
        for c in target:
            c = int(c)
            if c ^ flip:
                ans += 1
                flip ^= 1
        return ans

If you have any doubts regarding this problem or need the solution in other programming languages then leave a comment down below .

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More LeetCode solutions All coding problems MCQ practice