Minimum Operations to Make Binary Array Elements Equal to One II

Minimum Operations to Make Binary Array Elements Equal to One II - Problem

You are given a binary array nums. You can do the following operation on the array any number of times (possibly zero):

Choose any index i from the array and flip all the elements from index i to the end of the array.

Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [0,1,0]

› Output: 2

💡 Note: Flip at index 0: [0,1,0] → [1,0,1]. Flip at index 2: [1,0,1] → [1,1,0]. Need 2 operations total.

Example 2 — Already All Ones

$ Input: nums = [1,1,1]

› Output: 0

💡 Note: All elements are already 1, so no operations needed.

Example 3 — All Zeros

$ Input: nums = [0,0,0]

› Output: 1

💡 Note: Flip at index 0: [0,0,0] → [1,1,1]. Only 1 operation needed.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is that we can solve this greedily by scanning left to right and flipping whenever we encounter an effective 0. The greedy approach tracks the cumulative effect of previous flips to determine the current effective value. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n × n)	O(n)	Generate all possible operation sequences and find minimum
Greedy - Scan Left to Right	O(n)	O(1)	Scan array left to right, flip whenever we encounter a 0

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible flip sequences
For each sequence, simulate all operations
Check if result has all 1s
Return minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible flip sequences

Simulate Each

Apply operations and check result

Find Minimum

Return smallest valid operation count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int n) {
    int minOps = INT_MAX;
    
    // Try all possible combinations of flip operations
    for (int mask = 0; mask < (1 << n); mask++) {
        int* temp = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            temp[i] = nums[i];
        }
        int ops = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                ops++;
                // Flip from index i to end
                for (int j = i; j < n; j++) {
                    temp[j] = 1 - temp[j];
                }
            }
        }
        
        // Check if all elements are 1
        int allOnes = 1;
        for (int i = 0; i < n; i++) {
            if (temp[i] != 1) {
                allOnes = 0;
                break;
            }
        }
        
        if (allOnes && ops < minOps) {
            minOps = ops;
        }
        
        free(temp);
    }
    
    return minOps == INT_MAX ? -1 : minOps;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n possible combinations of operations, each taking O(n) time to simulate

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing array copies during simulation

⚡ Linearithmic Space

22.1K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler