Skip to main content
Talentd

Maximum Odd Binary Number - Solution & Explanation

EasyMathStringGreedy14 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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 <= 100
  • s consists only of '0' and '1'.
  • s contains at least one '1'.

Approach Overview

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 1: Approach 1: Sort and Place Last '1'

To form the maximum odd binary number from a given binary string, observe that the binary number should have '1' at the end to be odd. Among the remaining bits, arrange as many '1's as possible at the leading positions while maintaining the '1' at the end. This approach involves counting the occurrences of '1' and '0', then constructing the number.

  1. Count the '1's and '0's in the string.
  2. Ensure the last bit is '1', then place the rest of the '1's at the beginning and fill with '0's.

The program first counts the '1's and '0's. It reserves one '1' for the end to make the number odd. The rest of the '1's are placed at the beginning, and '0's fill the remaining positions before the final '1'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string as it needs one pass to count and another to construct.
Space Complexity: O(1) for the counting variables.

Try this approach in the editor →

Approach 2: Approach 2: Using Sorting

A different approach involves sorting the binary string while ensuring a '1' is at the end. To maximize the binary number, the initial part of the string should consist of leading '1's followed by '0's, then append a single '1' at the end to turn the number odd.

  1. Convert the string to a list and sort in descending order.
  2. Ensure the last position is '1'.

This solution sorts the string in descending order and ensures '1' is moved to the last position. Sorting places '1's before '0's. The trailing '1' ensures oddness.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) assuming sorting in place is allowed.

Try this approach in the editor →

Approach 3: Greedy

First, we count the number of '1's in the string s, denoted as cnt. Then, we place cnt - 1 '1's at the highest position, followed by the remaining |s| - cnt '0's, and finally add one '1'.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Sort and Place Last '1'

Time Complexity: O(n), where n is the length of the string as it needs one pass to count and another to construct.
Space Complexity: O(1) for the counting variables.

Approach 2: Using Sorting

Time Complexity: O(n log n) for sorting.
Space Complexity: O(1) assuming sorting in place is allowed.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Place Last '1' (Greedy Counting)O(n)O(n)Best general solution. Single pass counting and direct construction.
Using SortingO(n log n)O(n)Simple to implement when sorting utilities are convenient.

Video Solution

Maximum Odd Binary Number - Leetcode 2864 - Python • NeetCodeIO • 6,970 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Odd Binary Number easy or hard?
Maximum Odd Binary Number is classified as an Easy problem. The challenge is recognizing the greedy insight that an odd binary number must end with '1' and that maximizing the value means pushing the remaining '1's to the left.
Maximum Odd Binary Number Python/Java solution
In Python or Java, count the number of '1's in the string and construct the result using string repetition or a StringBuilder. Place count(1)-1 ones at the start, append zeros for the remaining positions, and finish with a single '1'. The implementation runs in O(n) time.
How to solve Maximum Odd Binary Number in O(n)?
Count how many '1's exist in the string. Build a new string with count(1)-1 leading '1's, followed by all zeros, and place a single '1' at the end. This guarantees the largest binary value while keeping the number odd, and it only requires one pass through the string.
What is the best approach for Maximum Odd Binary Number?
The optimal approach is a greedy counting method. Count the number of '1's in the binary string, place count(1)-1 ones at the beginning, all zeros next, and keep one '1' at the end to ensure the number is odd. This constructs the largest possible binary value in O(n) time.
Is Maximum Odd Binary Number asked at Google/Amazon/Meta?
Greedy string rearrangement problems like Maximum Odd Binary Number commonly appear in coding interviews at large tech companies. Variants of binary manipulation and greedy placement are frequently asked at companies such as Amazon, Google, and Meta during screening rounds.
What data structure is used in Maximum Odd Binary Number?
The solution primarily uses basic string manipulation and counting. Some implementations convert the string to a character array or list for easier modification, but the algorithm mainly relies on greedy placement rather than complex data structures.
What is the time complexity of Maximum Odd Binary Number?
The optimal greedy solution runs in O(n) time because the algorithm only scans the string once to count bits and then constructs the result. Space complexity is O(n) for the resulting string.

Ready to solve this problem?

Practice Maximum Odd Binary Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer