1529. Bulb Switcher IV

There are n light bulbs arranged in a row from left to right, numbered from 0 to n-1. Initially, all bulbs are turned off.

Your task is to make the state of the bulbs match the target configuration, where target[i] = 1 means the i-th bulb is on, and target[i] = 0 means the i-th bulb is off.

You have a switch that can flip the state of bulbs. The flip operation is defined as:

• Select any bulb (index i) in the current configuration
• Flip the state of each bulb from index i to n-1
• When flipping, a bulb with state 0 becomes 1, and a bulb with state 1 becomes 0

Return the minimum number of flips required to achieve the target configuration.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
From bulb 3 (index 2): "00000" -> "00111"
From bulb 1 (index 0): "00111" -> "11000"
From bulb 2 (index 1): "11000" -> "10111"
At least 3 flips are needed to achieve the target configuration.

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'

Approach 1: Direct Simulation

function minFlips(target) {
    let flips = 0;
    const length = target.length;
    const bulbs = new Array(length).fill('0');
    
    for (let i = 0; i < length; i++) {
        if (target[i] !== bulbs[i]) {
            flips++;
            for (let j = i; j < length; j++) {
                bulbs[j] = bulbs[j] === '0' ? '1' : '0';
            }
        }
    }
    return flips;
}

Note: The direct simulation approach may not be efficient for large inputs (up to 10^5) due to the nested loop, leading to timeout issues.

Approach 2: Optimized Solution

function minFlips(target) {
    let result = 0;
    let currentState = 0;
    
    for (let i = 0; i < target.length; i++) {
        if (target[i] !== currentState.toString()) {
            result++;
            currentState = currentState === 0 ? 1 : 0;
        }
    }
    return result;
}

Alternative Optimized Solution:

function minFlips(target) {
    const extendedTarget = "0" + target;
    let flips = 0;
    
    for (let i = 1; i < extendedTarget.length; i++) {
        if (extendedTarget[i] !== extendedTarget[i-1]) {
            flips++;
        }
    }
    return flips;
}

Explanation: The optimized solution works by noting that each flip operation affects all bulbs from a certain index to the end. Instead of simulating each flip, we can track the current state and count transitions between different states in the target configuration.