Maximum Odd Binary Number

Difficulty: Easy | Acceptance: 82.90% | Paid: No Topics: Math, String, Greedy

You are given a binary string s. You are allowed to rearrange the bits in any order (including the original order).

Return the maximum odd binary number that can be created from the bits in s.

A binary number x is called odd if its last digit is 1. For example, 101, 1101 are odd while 1010, 100 are not.

• Examples
• Constraints
• Greedy Construction
• Sorting
• Two Pointers

Examples

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[i] is either '0' or '1'.
s contains at least one '1'.

Greedy Construction

Intuition To maximize a binary number, we want the most significant bits (leftmost) to be ‘1’s. Since the number must be odd, the least significant bit (rightmost) must be ‘1’. Therefore, we place all ‘1’s at the beginning except for one, which we place at the very end. All ‘0’s fill the space in between.

Steps

• Count the number of ‘1’s in the string.
• Construct the result string by placing (count_ones - 1) ‘1’s, followed by (length - count_ones) ‘0’s, and finally a single ‘1’.

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

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once to count and once to build the result.
• Space: O(n) to store the result string.
• Notes: This is the most optimal approach for this problem.

Sorting

Intuition We can sort the string in descending order so that all ‘1’s come first. If the last character is ‘0’, we need to make the number odd by moving a ‘1’ to the end. We can simply swap the last ‘1’ with the last character.

Steps

• Convert the string to a character array.
• Sort the array in descending order.
• If the last character is ‘0’, find the last ‘1’ in the array and swap it with the last character.
• Convert the array back to a string.

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        chars = sorted(s, reverse=True)
        if chars[-1] == '0':
            i = len(chars) - 1
            while chars[i] == '0':
                i -= 1
            chars[i], chars[-1] = chars[-1], chars[i]
        return ''.join(chars)

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(n) to store the character array.
• Notes: Sorting is less efficient than the counting approach but is a straightforward brute-force method.

Two Pointers

Intuition We can use a two-pointer technique to move all ‘1’s to the left side of the array. Once all ‘1’s are clustered at the start, we swap the last ‘1’ with the last element to ensure the number is odd.

Steps

• Convert the string to a mutable array.
• Initialize a left pointer at 0.
• Iterate with a right pointer. If arr[right] is ‘1’, swap it with arr[left] and increment left.
• After the loop, all ‘1’s are at indices 0 to left-1. Swap the element at left-1 (the last ‘1’) with the last element in the array.
• Convert the array back to a string.

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        arr = list(s)
        left = 0
        for right in range(len(arr)):
            if arr[right] == '1':
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
        arr[left - 1], arr[-1] = arr[-1], arr[left - 1]
        return ''.join(arr)

Complexity

• Time: O(n) since we traverse the array once.
• Space: O(n) to store the character array (strings are immutable in many languages).
• Notes: This approach modifies the array in-place and is efficient, though slightly more complex to implement than the counting method.