1046. Flipping Every Switch From Here On

A row of m switches all start OFF, written as 0. One operation picks a position i and flips EVERY switch from i to the end of the row, turning each 0 into a 1 and each 1 into a 0.

A target pattern is given. Print the fewest operations that turn the all-off row into it.

10111 -> 3 flip from 0 -> 11111, flip from 1 -> 10000, flip from 2 -> 10111 101 -> 3 00000 -> 0 0011 -> 1 flip from position 2

## What most people try first

Search over sequences of operations. Each state is one of 2^m patterns and each state has m moves, so breadth first search is O(m * 2^m). That is fine for m = 12 and hopeless for the 100000 the input allows. It is also how the expected outputs in this problem were checked.

## Decide the switches left to right

Walk the row and keep track of what the leftmost switch you have not yet fixed currently reads. Call it state, starting at 0.

At position i, the switch reads state, because every flip so far that reached i also reached everything after it. If state already equals the target character, do nothing and move on. If it does not, flip from i, which costs one operation and sets state to the target character.

state = '0', ops = 0 for each character c of the target: if c != state: ops += 1 state = c

So the answer is simply the number of places where the target changes value, counting the very first character as a change if it is 1.

## Why the forced move is the only move

At position i, exactly one thing can still change that switch: an operation starting at or before i. Every such operation also flips everything to the right of i, so if you leave position i wrong and fix it later, that later fix disturbs every decision you have already made to the right of i, which is nothing yet, and also every decision to the LEFT of i, which is where the damage is: operations starting at or before i flip positions before i too, undoing them.

So each position must be correct by the time the sweep passes it, and the only way to correct it is one flip. Every flip the sweep performs is therefore forced, which makes the count both a lower bound and achievable at once.

## The starting state is 0, not the first character

The count is the number of adjacent differences PLUS one if the first character is 1. The cleanest way to say that is to seed state with '0' and let the first character be compared against it like any other. Seeding with the first character instead answers 10111 as 2, and that case is in the tests.

## Overflow

The answer is at most m = 100000. Nothing here is near the 32 bit limit of 2147483647.

## Cost

Time O(m). Space O(1).

Constraints - `1 ≤ m ≤ 100000` - the line contains only `0` and `1`