LeetCode Problem 2864

Difficulty: 🟢 Easy
Topics: Math, String, Greedy

Solution

LeetCode 2864 - Maximum Odd Binary Number

Problem Understanding

The problem gives us a binary string s, containing only '0' and '1' characters. We are allowed to rearrange the bits in any order we want, but we must use exactly the same bits that appear in the original string.

Our goal is to create the largest possible binary number that is also odd.

To understand what this means, recall two important properties of binary numbers:

1. A binary number is odd if and only if its last bit is '1'.
2. Larger binary numbers are created by placing more '1' bits toward the left, because leftmost positions have higher place values.

Therefore, we need to rearrange the bits so that:

• The final bit is '1', guaranteeing the number is odd.
• The remaining '1' bits are placed as far left as possible to maximize the value.

The problem guarantees that the input contains at least one '1', so it is always possible to construct an odd binary number.

The input size is small, with s.length <= 100, but the optimal solution is straightforward and linear.

Some important edge cases include:

• A string containing exactly one '1', such as "010".
• A string consisting entirely of '1' characters.
• A string of length 1, such as "1".
• Cases where many zeros exist and only one '1' is available.
• Cases where the bits are already arranged optimally.

The guarantee that at least one '1' exists eliminates the possibility of constructing an odd number from an all-zero string.

Approaches

Brute Force

A brute-force solution would generate every possible permutation of the binary string, filter out the permutations that represent odd numbers, and then select the largest one.

This approach is correct because it examines every possible arrangement and therefore cannot miss the optimal answer.

However, the number of permutations grows factorially. For a string of length n, there can be up to n! permutations. Even for relatively small values of n, this becomes computationally infeasible.

Since the input length can reach 100, a brute-force permutation approach is completely impractical.

Key Insight

To create an odd binary number, the last position must contain a '1'.

Suppose the string contains:

• ones occurrences of '1'
• zeros occurrences of '0'

One '1' must be reserved for the last position.

After reserving that final '1', we have:

• ones - 1 remaining '1' bits
• zeros zero bits

To maximize the binary value, every remaining '1' should be placed at the beginning of the string because earlier positions contribute more to the numerical value than later positions.

Therefore, the optimal arrangement is:

• All remaining '1' bits first
• Then all '0' bits
• Then the reserved final '1'

This directly constructs the largest possible odd binary number.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! × n)	O(n! × n)	Generate all permutations and select the largest odd one
Optimal	O(n)	O(n)	Count bits and construct the answer directly

Algorithm Walkthrough

1. Count the number of '1' characters in the string.

We need this count because one '1' must be placed at the end, while the remaining '1' bits should be placed at the front. 2. Count the number of '0' characters.

These zeros will occupy the middle section of the final arrangement. 3. Reserve one '1' for the final position.

Since the result must be odd, the last character must be '1'. 4. Place all remaining '1' bits at the beginning.

This maximizes the value because the most significant positions receive the largest possible bits. 5. Place all zeros after those leading ones.

Once all available leading positions are filled with '1', the zeros naturally follow. 6. Append the reserved '1' at the end.

This guarantees the resulting binary number remains odd. 7. Return the constructed string.

Why it works

The last bit determines whether a binary number is odd. Therefore, one '1' must occupy the final position.

After fixing the last position, every remaining position should be maximized. Since '1' is larger than '0', placing all remaining '1' bits in the most significant positions yields the largest possible binary value. Any arrangement that moves a '1' to the right and a '0' to the left would produce a smaller number. Thus, the construction

(ones - 1) leading ones + all zeros + final one

is optimal.

Python Solution

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

        return '1' * (ones - 1) + '0' * zeros + '1'

The implementation first counts how many '1' bits exist in the input. Since the problem guarantees at least one '1', we can safely reserve one of them for the final position.

The number of zeros is simply the total length minus the number of ones.

The result is then built in three parts:

1. ones - 1 leading '1' characters.
2. All zero characters.
3. A final '1'.

String multiplication makes this construction concise and efficient.

Go Solution

func maximumOddBinaryNumber(s string) string {
	ones := 0

	for _, ch := range s {
		if ch == '1' {
			ones++
		}
	}

	zeros := len(s) - ones

	result := ""

	for i := 0; i < ones-1; i++ {
		result += "1"
	}

	for i := 0; i < zeros; i++ {
		result += "0"
	}

	result += "1"

	return result
}

The Go solution follows exactly the same logic as the Python version. It counts the number of ones, computes the number of zeros, then constructs the answer in three sections.

Because the maximum string length is only 100, repeated string concatenation is perfectly acceptable here. For larger inputs, a strings.Builder could be used to reduce allocation overhead, but it is unnecessary for this constraint range.

Worked Examples

Example 1

Input

s = "010"

Step 1: Count bits

Value	Count
Ones	1
Zeros	2

Step 2: Reserve one final '1'

Remaining Ones	Reserved Final One
0	1

Step 3: Construct result

Section	Value
Leading ones	""
Zeros	"00"
Final one	"1"

Result:

"001"

Example 2

Input

s = "0101"

Step 1: Count bits

Value	Count
Ones	2
Zeros	2

Step 2: Reserve one final '1'

Remaining Ones	Reserved Final One
1	1

Step 3: Construct result

Section	Value
Leading ones	"1"
Zeros	"00"
Final one	"1"

Result:

"1001"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count bits and linear work to build the result
Space	O(n)	The output string itself contains n characters

The algorithm processes each character a constant number of times. No nested loops or expensive operations are performed. The dominant memory usage comes from constructing the final answer, which necessarily contains the same number of characters as the input.

Test Cases

sol = Solution()

assert sol.maximumOddBinaryNumber("010") == "001"      # example 1
assert sol.maximumOddBinaryNumber("0101") == "1001"    # example 2

assert sol.maximumOddBinaryNumber("1") == "1"          # minimum length
assert sol.maximumOddBinaryNumber("111") == "111"      # all ones
assert sol.maximumOddBinaryNumber("1000") == "0001"    # exactly one one
assert sol.maximumOddBinaryNumber("0001") == "0001"    # one one already at end
assert sol.maximumOddBinaryNumber("1100") == "1001"    # mixed bits
assert sol.maximumOddBinaryNumber("101010") == "110001" # alternating pattern
assert sol.maximumOddBinaryNumber("011111") == "111101" # many ones
assert sol.maximumOddBinaryNumber("0000001") == "0000001" # many zeros

Test Case Summary

Test	Why
"010"	Official example with one '1'
"0101"	Official example with multiple '1' bits
"1"	Smallest valid input
"111"	All bits are ones
"1000"	Exactly one '1' available
"0001"	Single '1' already at the end
"1100"	Typical mixed input
"101010"	Alternating pattern
"011111"	Large concentration of ones
"0000001"	Large concentration of zeros

Edge Cases

Only One '1' Exists

Consider an input such as "1000" or "010". Since an odd binary number must end with '1', the only available '1' is forced into the last position. Every other position must therefore contain '0'. A buggy solution might incorrectly place the lone '1' at the front to maximize value, producing an even number. The implementation correctly reserves the only '1' for the final position.

All Characters Are '1'

For an input such as "11111", there are no zeros. The optimal arrangement is identical to the original string because every position already contains the largest possible bit. The formula naturally produces '1' * (ones - 1) + '' + '1', resulting in the same string.

Input Length Is One

The smallest valid input is "1". Here, ones = 1 and zeros = 0. The expression becomes:

'1' * 0 + '0' * 0 + '1'

which correctly evaluates to "1". This confirms that the implementation handles the minimum constraint without special-case logic.

Many Zeros and Few Ones

For inputs such as "0000001", most positions contain zeros. The algorithm still works because it reserves one '1' for the end and places any remaining ones at the beginning. Since there are no remaining ones in this example, the result becomes all zeros followed by a final '1', which is the largest odd arrangement possible.