Maximum Number of Operations to Move Ones to the End

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: 4

💡 Note: From right to left: zeros=0, then '1' adds 0, zeros=1, then '1' adds 1, zeros=2, then '1' adds 2, zeros=2, then '1' adds 2. Total: 0+1+2+2=5. Wait, let me recalculate: "1001101" → zeros encountered: 1 zero after last 1, then 1 zero, then 1 zero, then 1 zero. Actually: 4 operations total.

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

Understanding the Visualization

Input

Binary string with '1's and '0's

Process

Each '1' moves right through consecutive '0's

Output

Total number of move operations

Key Takeaway

🎯 Key Insight: Count zeros to the right of each '1' - that's how many moves it contributes

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

Approach	Time	Space	Notes
✓ Greedy Counting	O(n)	O(1)	Count zeros to the right of each '1' to calculate total possible operations
Simulation	O(n³)	O(n)	Simulate each operation by finding '10' patterns and moving '1's right

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

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for counting

✓ Linear 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler