1097MediumArrayBit ManipulationQueueSliding WindowPrefix Sum

Raising Every Flag With Triple Flips

Tracked in this browser only

Trains the technique from

LeetCode 3191Minimum Operations to Make Binary Array Elements Equal to One I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A row of flags holds only the values 0 and 1. One move picks any three neighbouring flags and flips each of them: a 0 becomes a 1 and a 1 becomes a 0.

Return the fewest moves needed to leave every flag showing 1, or -1 when no number of moves can do it.

Examples

Example 1

Input: flags = [0, 0, 0]
Output: 1

One move over all three flags raises the whole row.

Example 2

Input: flags = [0, 0, 1, 0, 0]
Output: 2

Flipping the first three flags leaves 1, 1, 0, 0, 0 and flipping the last three finishes the row.

Example 3

Input: flags = [1, 1, 1, 0, 1]
Output: -1

The single 0 sits second from the end. Working left to right nothing needs flipping, and the two trailing flags start no window, so that 0 can never be raised.

Constraints

3 <= flags.length <= 10^5
0 <= flags[i] <= 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_operations(flags: list[int]) -> int:

Java

public int minOperations(int[] flags)

The intended approach

Time O(n) over the row.Space O(n) for the working copy of the row.

Only the windows starting at positions `0` through `n - 3` exist, and the very first flag sits in exactly one of them. So whether that window is used is forced: use it when the first flag shows `0`, leave it alone otherwise. Once that choice is made the first flag is settled forever and the same argument applies to the second flag with the window starting at position `1`, and so on. That makes a single left-to-right pass the whole method. Walk the positions that can start a window, flip the three flags there whenever the leftmost of them shows `0`, and count the flips. Every flip was forced, so no shorter run of moves exists and no different run reaches the goal either. The last two flags start no window, so nothing is left that can change them. If the pass leaves either of them showing `0` the row simply cannot be raised.

Pythonentry point: min_operations

def min_operations(flags):
    n = len(flags)
    row = list(flags)
    moves = 0
    for i in range(n - 2):
        if row[i] == 0:
            row[i] = 1
            row[i + 1] ^= 1
            row[i + 2] ^= 1
            moves += 1
    if row[n - 2] == 1 and row[n - 1] == 1:
        return moves
    return -1

The obvious version

Pack the row into a bit pattern and walk outwards from it one move at a time, breadth first, until the all-ones pattern turns up. The first time it appears is by definition the fewest moves, and if the search runs dry the row cannot be raised. Costs two to the power of the row length.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_operations(flags):
    from collections import deque
    n = len(flags)
    start = 0
    for i in range(n):
        if flags[i]:
            start |= 1 << i
    goal = (1 << n) - 1
    if start == goal:
        return 0
    seen = {start: 0}
    queue = deque([start])
    while queue:
        state = queue.popleft()
        step = seen[state]
        for i in range(n - 2):
            nxt = state ^ (7 << i)
            if nxt == goal:
                return step + 1
            if nxt not in seen:
                seen[nxt] = step + 1
                queue.append(nxt)
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in