Flip the Tail

Medium

You are given an array bits of zeros and ones. In one operation you pick a position i and flip every element from i to the end of the array: zeros become ones and ones become zeros. Return the minimum number of operations after which the array contains only ones.

Example 1

bits=[1, 1, 0, 0, 1] → 2

Flip the tail from position 2: [1, 1, 1, 1, 0]. Then the tail from position 4: all ones. 2 flips in total.

Example 2

bits=[0, 0, 0] → 1

A single flip of the whole array from position 0 is enough.

Example 3

bits=[1, 0, 1, 0] → 3

Constraints

1 ≤ len(bits) ≤ 10⁵
bits[i] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Reach the Last Cell Medium As Many Trades as You Like Medium Longest Seesaw Subsequence Medium Fewest Meetings to Cancel Medium

Input

bits=[1, 1, 0, 0, 1]

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.