To solve Maximum Odd Binary Number, immediately place one '1' at the end to satisfy the odd constraint. Arrange remaining '1's to the left for maximal value. This ensures a greedy choice combined with invariant validation, producing the largest possible odd binary number efficiently.
Problem Statement
Given a binary string s containing at least one '1', rearrange the bits so that the resulting binary number is odd and as large as possible. You must return a string representing this maximum odd binary number.
Each '1' except for the one at the least significant position can be freely rearranged to maximize the number. The string contains only '0's and '1's, and its length ranges from 1 to 100.
Examples
Example 1
Input: s = "010"
Output: "001"
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"
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 Approach
Count and Isolate Last '1'
Count all '1's in the string. Reserve one '1' for the least significant position to satisfy the odd number constraint.
Greedy Placement of Remaining Bits
Place all remaining '1's to the left in the string followed by all '0's. This greedy placement ensures the largest binary value before the final '1'.
Combine and Return
Append the reserved '1' at the end. Concatenate the arranged '1's, '0's, and the final '1' to form the maximum odd binary string and return it.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
The algorithm scans the string once to count '1's and then constructs the result in a single pass, resulting in O(n) time and O(n) space complexity.
What Interviewers Usually Probe
- Ask why placing a '1' at the end guarantees an odd number.
- Check if candidates correctly separate the last '1' from the remaining bits.
- Expect explanation of greedy choice for maximizing the binary value.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to reserve one '1' at the least significant position, producing an even number.
- Reordering '0's and '1's incorrectly, reducing the maximum value.
- Assuming multiple '1's can occupy the last position, violating the odd constraint.
Follow-up variants
- Find the maximum even binary number by placing '0' at the least significant bit.
- Count the number of maximum odd binary numbers possible from the same string.
- Extend the problem to ternary strings with a similar odd-value constraint.
How GhostInterview Helps
- Immediately highlights the greedy plus invariant pattern, guiding bit placement efficiently.
- Validates edge cases like strings with a single '1' without manual calculation.
- Provides step-by-step construction for the largest odd binary number in seconds.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern in Maximum Odd Binary Number?
The key pattern is a greedy choice with invariant validation: place one '1' at the end and maximize remaining bits.
Can the last bit be '0' in the maximum odd binary number?
No, the last bit must be '1' to ensure the number is odd.
How do I handle strings with only one '1'?
Place that '1' at the end; all preceding bits are '0's, forming the correct maximum odd binary number.
What is the time complexity of the optimal solution?
It is O(n) because counting and arranging bits requires a single pass through the string.
Does the order of '0's matter in the solution?
Yes, '0's should follow all '1's except the reserved last '1' to maximize the binary value.
Need direct help with Maximum Odd Binary Number instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Maximum Odd Binary Number from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Minimize operations to make a number divisible by 25 by deleting digits. Use greedy choice and invariant validation.
Open problem page#2842 Count K-Subsequences of a String With Maximum BeautyDetermine the number of k-length unique subsequences in a string that maximize the sum of character frequencies efficiently using greedy methods.
Open problem page#3014 Minimum Number of Pushes to Type Word ICalculate the minimum pushes to type a word using a remapped telephone keypad with greedy allocation of letters.
Open problem page