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 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
    }
    

All Problems

All Solutions