Maximum Number of Operations to Move Ones to the End - Problem

You are given a binary string s. You can perform the following operation on the string any number of times:

Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.

Move the character s[i] to the right until it reaches the end of the string or another '1'.

For example, for s = "010010", if we choose i = 1, the resulting string will be s = "001010".

Return the maximum number of operations that you can perform.

Input & Output

Example 1 — Basic Case

$ Input: s = "1001101"

› Output: 5

💡 Note: From right to left: '1' sees 0 zeros, '0' increments zeros to 1, '1' sees 1 zero (ops=1), '1' sees 1 zero (ops=2), '0' increments zeros to 2, '0' increments zeros to 3, '1' sees 3 zeros (ops=5). Total: 5 operations.

Example 2 — All Ones

$ Input: s = "1111"

› Output: 0

💡 Note: No zeros to move through, so no operations possible

Example 3 — Alternating Pattern

$ Input: s = "10101"

› Output: 3

💡 Note: From right: '1' sees 0 zeros, '0' increments zeros to 1, '1' sees 1 zero (ops=1), '0' increments zeros to 2, '1' sees 2 zeros (ops=3)

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of '0' and '1'

Visualization

Tap to expand

Asked in

G Google 12 a Amazon 8 M Microsoft 5

The key insight is that each '1' can move through all '0's to its right. The optimal approach scans right-to-left, counting zeros and adding them to operations for each '1' encountered. Time: O(n), Space: O(1)

Common Approaches

✓ Greedy Counting

⏱️ Time: O(n) Space: O(1)

Scan from right to left, keeping track of zeros encountered. Each '1' can move through all zeros to its right, contributing that many operations to the total.

Simulation

⏱️ Time: O(n³) Space: O(n)

Repeatedly scan the string for '10' patterns, move each '1' as far right as possible, and count operations. Continue until no more operations are possible.

Greedy Counting — Algorithm Steps

Scan string from right to left
Count zeros encountered so far
For each '1', add zero count to total operations
Continue until string is processed

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Right

Process string from right to left

Count Zeros

Track zeros seen so far

Add to Total

Each '1' contributes zeros count to operations

Code -

solution.c — C

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

int solution(char* s) {
    int n = strlen(s);
    int operations = 0;
    int zeros = 0;
    
    // Scan from right to left
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '0') {
            zeros++;
        } else { // s[i] == '1'
            operations += zeros;
        }
    }
    
    return operations;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string from right to left

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra variables for counting

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Maximum Number of Operations to Move Ones to the End - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler