Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1529.html
1529. Bulb Switcher IV
Level
Medium
Description
There is a room with n
bulbs, numbered from 0
to n1
, 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 ith 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
ton1
.
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 }