##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1529.html

# 1529. Bulb Switcher IV

Medium

## Description

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'

## Solution

Obviously, if target.charAt(0) == '1', then there must be a flip operation at index 0. Since a flip operation that chooses index i flips all the bulbs from index i to index n - 1, if target.charAt(i - 1) != target.charAt(i) for 0 < i < n, then there must be a flip operation at index i. Otherwise, no flip operation is needed at index i. Therefore, simply count the number of indices where the state of the bulb is different from the state of the previous bulb. If the bulb at index 0 is 1, then it is also flipped.

• class Solution {
public int minFlips(String target) {
int flips = 0;
char prev = '0';
int length = target.length();
for (int i = 0; i < length; i++) {
char curr = target.charAt(i);
if (curr != prev)
flips++;
prev = curr;
}
return flips;
}
}

############

class Solution {
public int minFlips(String target) {
int ans = 0;
for (int i = 0; i < target.length(); ++i) {
int v = target.charAt(i) - '0';
if (((ans & 1) ^ v) != 0) {
++ans;
}
}
return ans;
}
}

• class Solution:
def minFlips(self, target: str) -> int:
ans = 0
for v in target:
if (ans & 1) ^ int(v):
ans += 1
return ans


• class Solution {
public:
int minFlips(string target) {
int ans = 0;
for (char c : target) {
int v = c - '0';
if ((ans & 1) ^ v) {
++ans;
}
}
return ans;
}
};

• func minFlips(target string) int {
ans := 0
for _, c := range target {
v := int(c - '0')
if ((ans & 1) ^ v) != 0 {
ans++
}
}
return ans
}
`