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.

• Java
• Python
• C++
• Go

• 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