Problem

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

Examples

Example 1

1
2
3

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Example 2

1
2
3

Input: s = "0101"
Output: "1001"
Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".

Constraints

  • 1 <= s.length <= 100
  • s consists only of '0' and '1'.
  • s contains at least one '1'.

Solution

Method 1 – Greedy Rearrangement

Intuition

To get the maximum odd binary number, we want as many ‘1’s as possible at the left (most significant bits), but the last bit must be ‘1’ (to make it odd). So, put all ‘1’s except one at the front, all ‘0’s after, and one ‘1’ at the end.

Approach

  1. Count the number of ‘1’s in the string.
  2. The result is: (count of ‘1’s - 1) ‘1’s, then all ‘0’s, then one ‘1’ at the end.
  3. The number of ‘0’s is the length of the string minus the count of ‘1’s.
  4. Return the constructed string.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int ones = count(s.begin(), s.end(), '1');
        int zeros = s.size() - ones;
        return string(ones - 1, '1') + string(zeros, '0') + '1';
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func maximumOddBinaryNumber(s string) string {
    ones := 0
    for _, c := range s {
        if c == '1' {
            ones++
        }
    }
    zeros := len(s) - ones
    return strings.Repeat("1", ones-1) + strings.Repeat("0", zeros) + "1"
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public String maximumOddBinaryNumber(String s) {
        int ones = 0;
        for (char c : s.toCharArray()) if (c == '1') ones++;
        int zeros = s.length() - ones;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ones - 1; i++) sb.append('1');
        for (int i = 0; i < zeros; i++) sb.append('0');
        sb.append('1');
        return sb.toString();
    }
}
1
2
3
4
5
6
7

class Solution {
    fun maximumOddBinaryNumber(s: String): String {
        val ones = s.count { it == '1' }
        val zeros = s.length - ones
        return "1".repeat(ones - 1) + "0".repeat(zeros) + "1"
    }
}
1
2
3
4
5

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        ones = s.count('1')
        zeros = len(s) - ones
        return '1' * (ones - 1) + '0' * zeros + '1'
1
2
3
4
5
6
7

impl Solution {
    pub fn maximum_odd_binary_number(s: String) -> String {
        let ones = s.chars().filter(|&c| c == '1').count();
        let zeros = s.len() - ones;
        format!("{}{}1", "1".repeat(ones - 1), "0".repeat(zeros))
    }
}
1
2
3
4
5
6
7

class Solution {
    maximumOddBinaryNumber(s: string): string {
        const ones = s.split('').filter(c => c === '1').length;
        const zeros = s.length - ones;
        return '1'.repeat(ones - 1) + '0'.repeat(zeros) + '1';
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the string once.
  • 🧺 Space complexity: O(n) — For the output string.