Maximum Odd Binary Number

How it works

We can rearrange the string in-place using a two-pointer technique similar to the partition step in quicksort. We move all 1s to the left side of the array, then swap one 1 to the last position.

This achieves the same result as sorting but with a single O(n) pass.

Steps

1. Convert the string to a character array.
2. Use a left pointer starting at 0. Iterate through the array with index i.
3. Whenever s[i] == '1', swap s[i] with s[left] and increment left.
4. After the loop, all 1s are at positions 0 to left - 1.
5. Swap s[left - 1] with s[n - 1] to place one 1 at the end.
6. Return the resulting string.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Forgetting That Odd Numbers Must End With 1

The defining property of an odd binary number is that its least significant bit (last character) must be '1'. A common mistake is placing all 1s at the beginning without reserving one for the end, resulting in an even number. Always ensure exactly one '1' is placed at the last position.

Assuming the Input Always Has Multiple 1s

When the input contains only a single '1', the only valid output is that '1' at the end with all '0's before it. Failing to handle this edge case (e.g., trying to place count - 1 ones when count is 1) can cause index errors or incorrect string construction.

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        s = [c for c in s]
        left = 0

        for i in range(len(s)):
            if s[i] == "1":
                s[i], s[left] = s[left], s[i]
                left += 1
        s[left - 1], s[len(s) - 1] = s[len(s) - 1], s[left - 1]
        return "".join(s)

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        vector<char> arr(s.begin(), s.end());
        int left = 0;

        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == '1') {
                swap(arr[left], arr[i]);
                left++;
            }
        }

        swap(arr[left - 1], arr[arr.size() - 1]);
        return string(arr.begin(), arr.end());
    }
};