Maximum Odd Binary Number

Easy

#2561Time: O(N log N), where N is the length of the string. The performance is dominated by the sorting operation.Space: O(N), to store the character array. In Java, strings are immutable, so creating a character array for sorting is necessary.

Patterns

Math Greedy

Data structures

String

Prompt

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.

Example 1:

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:

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'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves sorting the characters of the string to group the '1's and '0's. By sorting in descending order, we get the largest possible binary number. A final swap is needed to ensure the number is odd.

Algorithm

Convert the input string s into a character array chars.
Sort chars in descending order. For characters, this means '1' comes before '0'.
Find the index of the last '1' in the sorted array.
Swap the character at this index with the character at the last position of the array (s.length() - 1).
Convert the modified character array back to a string.

Walkthrough

The core idea is that the largest binary number is formed by placing as many '1's as possible in the most significant (leftmost) positions. Sorting the binary string in descending order achieves this, resulting in a string like 11...100...0. However, this number is even (unless it contains no '0's). To make it odd, the last digit must be '1'. Since the input is guaranteed to have at least one '1', we can always make an odd number. The algorithm first sorts the characters in descending order and then performs a swap to move one '1' to the end, thus satisfying both conditions of being maximum and odd.

1import java.util.Arrays;2import java.util.Collections;3 4class Solution {5    public String maximumOddBinaryNumber(String s) {6        int n = s.length();7        Character[] chars = new Character[n];8        for (int i = 0; i < n; i++) {9            chars[i] = s.charAt(i);10        }11 12        // Sort in descending order ('1's first, then '0's)13        Arrays.sort(chars, Collections.reverseOrder());14 15        // Find the last '1' and swap it with the last element16        // to make the number odd.17        for (int i = n - 1; i >= 0; i--) {18            if (chars[i] == '1') {19                // Swap chars[i] with the last element20                char temp = chars[i];21                chars[i] = chars[n - 1];22                chars[n - 1] = temp;23                break;24            }25        }26 27        StringBuilder result = new StringBuilder(n);28        for (char c : chars) {29            result.append(c);30        }31        return result.toString();32    }33}

Complexity

Time

O(N log N), where N is the length of the string. The performance is dominated by the sorting operation.

Space

O(N), to store the character array. In Java, strings are immutable, so creating a character array for sorting is necessary.

Trade-offs

Pros

Relatively straightforward to conceptualize if one thinks of rearranging bits as a sorting problem.

Cons

Sub-optimal time complexity compared to linear-time solutions.
The logic for the final swap can be slightly more complex than a direct construction method.

This is a highly efficient and straightforward approach. It relies on the logical construction of the target number based on the properties of maximum and odd binary numbers. We simply count the occurrences of '1's and '0's and then build the result string directly according to the derived optimal structure.

Algorithm

Iterate through the input string s to count the total number of '1's (onesCount).
The number of '0's is s.length() - onesCount.
Initialize a StringBuilder to build the result.
Append onesCount - 1 characters of '1' to the builder.
Append zerosCount characters of '0' to the builder.
Append a single '1' to the builder.
Convert the StringBuilder to a string and return it.

Walkthrough

To form the maximum odd binary number, we must satisfy two conditions:

The number must be odd, which requires its last bit to be '1'.
The number must be as large as possible, which means the remaining '1's should be placed at the most significant (leftmost) positions.

This leads to a simple structure for the result: (all other '1's) + (all '0's) + (one '1'). The algorithm implements this construction directly.

1class Solution {2    public String maximumOddBinaryNumber(String s) {3        int onesCount = 0;4        int n = s.length();5        for (char c : s.toCharArray()) {6            if (c == '1') {7                onesCount++;8            }9        }10        int zerosCount = n - onesCount;11 12        StringBuilder result = new StringBuilder();13 14        // 1. Append all '1's except one for the most significant part15        for (int i = 0; i < onesCount - 1; i++) {16            result.append('1');17        }18 19        // 2. Append all '0's for the middle part20        for (int i = 0; i < zerosCount; i++) {21            result.append('0');22        }23 24        // 3. Append the last '1' to make the number odd25        result.append('1');26 27        return result.toString();28    }29}

Complexity

Time

O(N), where N is the length of the string. We perform a single pass to count the characters and another effective pass to construct the result string.

Space

O(N), to store the `StringBuilder` and the final result string. This is optimal as a new string of length N must be returned.

Trade-offs

Pros

Optimal time complexity of O(N).
Simple and direct logic, making it easy to implement and less prone to errors.

Cons

Requires extra space to build the new string, although this is generally unavoidable for languages with immutable strings.

Solutions

Solution

1class Solution:2    def maximumOddBinaryNumber(self, s: str) -> str: cnt = s . count("1") return "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"

1class Solution {2public3  String maximumOddBinaryNumber(String s) {4    int cnt = 0;5    for (char c : s.toCharArray()) {6      if (c == '1') {7        ++cnt;8      }9    }10    return "1".repeat(cnt - 1) + "0".repeat(s.length() - cnt) + "1";11  }12}

1class Solution {2public:3  string maximumOddBinaryNumber(string s) {4    int cnt = count_if(s.begin(), s.end(), [](char c) { return c == '1'; });5    string ans;6    for (int i = 1; i < cnt; ++i) {7      ans.push_back('1');8    }9    for (int i = 0; i < s.size() - cnt; ++i) {10      ans.push_back('0');11    }12    ans.push_back('1');13    return ans;14  }15};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem