Skip to content

Latest commit

 

History

History
93 lines (82 loc) · 2.17 KB

1529. Bulb Switcher IV.md

File metadata and controls

93 lines (82 loc) · 2.17 KB

1529. Bulb Switcher IV

the second one in Weekly Contest 199.

Difficulty : Medium

Related Topics : String

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

  • mine
    • Java
      • Runtime: 4 ms, faster than 99.52, Memory Usage: 39.9 MB, less than 100.00% of Java online submissions 
        //O(N)time
//O(N)space
public int minFlips(String target) {
    char[] arr = target.toCharArray();
    int n = arr.length;
    char before = arr[n - 1];
    int res = 0;
    for(int i = n - 1; i >= 0; i--){
        if(before == arr[i]){
            continue;
        }
        before = arr[i];
        res++;
    }
    if(arr[0] == '1'){
        res++;
    }
    return res;
}