Problem Description

You are given a binary string s (containing only '0's and '1's) that has at least one '1' in it.

Your task is to rearrange the bits in the string to create the largest possible odd binary number.

A binary number is odd if and only if its least significant bit (rightmost bit) is '1'. To make the number as large as possible while keeping it odd, you need to:

• Ensure the rightmost bit is '1' (to make it odd)
• Place the remaining '1's as far left as possible (to maximize the value)
• Fill the remaining positions with '0's

For example, if you have the string "010", you can rearrange it to "001" to create the maximum odd binary number.

The solution counts the total number of '1's in the string (let's call it cnt). Then it constructs the result by:

1. Placing cnt - 1 ones at the beginning (leftmost positions)
2. Placing all the zeros in the middle
3. Placing exactly one '1' at the end (to ensure the number is odd)

The formula "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1" achieves this arrangement, where:

• "1" * (cnt - 1) creates the leading ones
• (len(s) - cnt) * "0" adds all the zeros
• + "1" adds the final '1' to make the number odd

Note that the resulting string can have leading zeros, which is allowed in this problem.

Intuition

To find the maximum odd binary number, we need to understand two key concepts:

1. What makes a binary number odd? A binary number is odd when its least significant bit (rightmost bit) is '1'. This is non-negotiable - we must have a '1' at the end.

2. What makes a binary number larger? In binary representation, bits on the left have higher positional values. Each bit position represents a power of 2, with leftmost bits having the highest powers. Therefore, to maximize a binary number, we want to place '1's as far left as possible.

Given these two constraints, the strategy becomes clear:

• We must reserve one '1' for the rightmost position (to ensure the number is odd)
• All remaining '1's should be moved to the leftmost positions (to maximize the value)
• All '0's naturally fill the middle positions

Think of it like distributing weights on a balance scale - you want the heaviest weights (the '1's) on the far left to tip the scale as much as possible, but you must keep exactly one weight on the far right.

For example, if we have three '1's and two '0's in our string:

• Reserve one '1' for the last position
• Place the remaining two '1's at the beginning
• Fill the middle with the '0's
• Result: "11001"

This greedy approach guarantees the maximum value because every '1' (except the mandatory last one) is placed in the highest possible position. The formula "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1" directly implements this strategy by constructing the string in three parts: leading ones, middle zeros, and the final one.

Learn more about Greedy and Math patterns.

Solution Approach

The solution uses a greedy approach to construct the maximum odd binary number. Here's the step-by-step implementation:

Step 1: Count the '1's

cnt = s.count("1")

First, we count how many '1's are present in the input string. This tells us how many '1's we have to work with.

Step 2: Construct the result string

return "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"

The construction happens in three parts:

1. Leading ones: "1" * (cnt - 1)

   • We place cnt - 1 ones at the beginning of the string
   • We subtract 1 because we need to reserve one '1' for the last position
   • These leading '1's maximize the binary value

2. Middle zeros: (len(s) - cnt) * "0"

   • The total number of '0's in the original string is len(s) - cnt
   • All zeros are placed in the middle section
   • This keeps all the '1's at positions of maximum significance (except the last one)

3. Trailing one: + "1"

   • We append exactly one '1' at the end
   • This ensures the resulting binary number is odd

Time Complexity: O(n) where n is the length of the string

• Counting '1's takes O(n) time
• String construction takes O(n) time

Space Complexity: O(n) for storing the result string

The algorithm is optimal because it places each '1' (except the mandatory last one) in the highest possible position, guaranteeing the maximum value while maintaining the odd property.

Example Walkthrough

Let's walk through the solution with the string s = "0101".

Step 1: Count the '1's

• Count all '1's in the string: s = "0101" has two '1's
• cnt = 2

Step 2: Determine the arrangement

• We need to keep one '1' at the end (to make it odd)
• So we can place cnt - 1 = 2 - 1 = 1 one at the beginning
• The number of '0's is len(s) - cnt = 4 - 2 = 2

Step 3: Construct the result Using the formula: "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"

• Leading ones: "1" * 1 = "1"
• Middle zeros: "0" * 2 = "00"
• Trailing one: "1"
• Result: "1" + "00" + "1" = "1001"

Verification:

• Original string "0101" in binary = 5 in decimal
• Rearranged string "1001" in binary = 9 in decimal
• 1001 is odd (ends with '1') ✓
• 1001 is the maximum possible odd arrangement ✓

Let's trace through another example with more '1's: s = "11100"

Step 1: Count '1's → cnt = 3

Step 2: Arrangement planning

• Reserve 1 for the end
• Place 3 - 1 = 2 ones at the beginning
• Place 5 - 3 = 2 zeros in the middle

Step 3: Build result

• "1" * 2 + "0" * 2 + "1" = "11001"

This gives us the maximum odd binary number possible with three '1's and two '0's.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The time complexity is determined by:

• s.count("1") iterates through the entire string once to count the occurrences of "1", which takes O(n) time
• String concatenation operations "1" * (cnt - 1) takes O(cnt - 1) time
• String concatenation (len(s) - cnt) * "0" takes O(len(s) - cnt) time
• The final concatenation of the three parts takes O(n) time in total
• len(s) is O(1) operation

Since all operations are either O(1) or O(n), the overall time complexity is O(n), where n is the length of the string s.

Space Complexity: O(n)

The space complexity is determined by:

• The output string that is constructed has the same length as the input string s, requiring O(n) space
• The variable cnt uses O(1) space
• The intermediate string constructions during concatenation may use temporary space of O(n)

Therefore, the overall space complexity is O(n), where n is the length of the string s.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Edge Cases with Exactly One '1'

A common mistake is not considering what happens when the input string contains exactly one '1'. In this case, cnt - 1 = 0, meaning there are no leading ones to place.

Incorrect approach:

# This might fail or produce incorrect results for edge cases
if s.count("1") == 1:
    # Special handling needed

Why the given solution works: The formula "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1" naturally handles this case:

• When cnt = 1: "1" * 0 + zeros + "1" = zeros + "1"
• This correctly places all zeros first, then the single '1' at the end

2. Forgetting to Reserve a '1' for the Last Position

Some might try to place all '1's at the beginning without reserving one for making the number odd:

Incorrect:

# This creates an even number!
result = "1" * ones_count + "0" * zeros_count

Correct approach: Always reserve one '1' for the last position and only use cnt - 1 ones for the leading positions.

3. Misunderstanding Binary Number Significance

Some might think that spreading '1's throughout the string could be beneficial, but in binary representation, leftmost positions have exponentially higher values.

Example:

• "1100001" (value: 97) is much larger than "1010101" (value: 85)
• Even though both have four '1's, clustering them to the left (except the last one) maximizes the value

4. Assuming No Leading Zeros Are Allowed

The problem statement allows leading zeros in the result. Don't add unnecessary complexity by trying to avoid them:

Unnecessary complexity:

# Trying to avoid leading zeros when not required
if ones_count == 1:
    return "1"  # This is wrong if len(s) > 1

Correct understanding: The result "0001" is a valid representation of the odd number 1 in this problem context.