Watch 10 video solutions for Maximum Odd Binary Number, a easy level problem involving Math, String, Greedy. This walkthrough by NeetCodeIO has 6,898 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100s consists only of '0' and '1'.s contains at least one '1'.Problem Overview: You are given a binary string s. Rearrange its characters so the resulting binary number is the largest possible odd value. An odd binary number must end with '1', so the challenge is placing the remaining bits to maximize the value while keeping that constraint.
Approach 1: Sort and Place Last '1' (Greedy, O(n) time, O(n) space)
The key observation is that an odd binary number must end with 1. To maximize the value, you want as many 1s as possible toward the left (most significant positions). Count how many 1s exist in the string. Place count(1) - 1 ones at the beginning, then all zeros in the middle, and reserve exactly one 1 for the final position. This greedy arrangement guarantees the largest possible binary value while satisfying the odd requirement. The algorithm scans the string once to count bits and constructs the result directly, giving O(n) time complexity and O(n) space for the output string. This approach uses simple string construction and works well for problems involving greedy decisions on string data.
Approach 2: Using Sorting (O(n log n) time, O(n) space)
Another method is to treat the string as a list of characters and sort it in descending order so that all 1s appear before 0s. After sorting, move one 1 to the final position to guarantee the number is odd. This produces a valid maximum arrangement because sorting ensures the highest bits appear first. The downside is the sorting step, which costs O(n log n) time compared to the linear greedy solution. Space complexity remains O(n) due to storing the sorted sequence. This approach is easier to reason about initially but is less efficient than counting-based greedy logic.
Recommended for interviews: The greedy counting approach is the expected solution. Interviewers want to see that you recognize the mathematical constraint that odd numbers end with 1 and that maximizing a binary value means pushing 1s to the left. Implementing it with a single pass and direct construction demonstrates strong understanding of math-based reasoning combined with greedy optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Place Last '1' (Greedy Counting) | O(n) | O(n) | Best general solution. Single pass counting and direct construction. |
| Using Sorting | O(n log n) | O(n) | Simple to implement when sorting utilities are convenient. |