Minimum Movement Cost to Segregate Binary Digits
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Minimum Movement Cost to Segregate Binary Digits
Given a binary string, repeatedly move a `1` to the right across adjacent `0` characters until all zeros precede all ones. Moving a `1` by one position costs 1. Return the minimum total movement cost. The relative order of equal digits is irrelevant.
## Function Contract
Implement `segregation_cost(s) -> int`.
## Constraints
- 0 <= string length <= 200000.
- The string contains only `0` and `1`.
- Each adjacent swap of `10` to `01` costs one.
- The answer fits in a signed 64-bit integer.
## Examples
```text
s = "01010"
output = 3
```
```text
s = "00011"
output = 0
```
```hint Check already segregated inputs
Inputs containing only one digit, all zeros before all ones, or the empty string should require no movement.
```
```hint Use a wide result
An alternating long string can require more total movement than fits in a signed 32-bit integer.
```
Quick Answer: Given a binary string, repeatedly move a `1` to the right across adjacent `0` characters until all zeros precede all ones. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given a binary string, repeatedly move a `1` right across an adjacent `0` until all zeros precede all ones. Each adjacent exchange of `10` to `01` costs one. Return the minimum total cost. The result must use a wide integer type where the language requires it.
Constraints
- 0 <= len(s) <= 200000, and every character is either 0 or 1.
- Each adjacent exchange of 10 to 01 costs exactly one.
- The answer fits in a signed 64-bit integer and is at most 10^10 under the length bound, which is also within JavaScript's exact-integer range.
Examples
Input: ('',)
Expected Output: 0
Explanation: The empty string requires no movement.
Input: ('0',)
Expected Output: 0
Explanation: A single zero is already segregated.
Hints
- Check the empty string, strings containing only one digit, and strings already written as zeros followed by ones.
- Compare one isolated zero after several ones with several zeros after one isolated one.
- Use a maximum-length case whose correct cost exceeds 2^31 - 1 to check result width.