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.

Description Hints 1 Solution Video 9:42

2864. Maximum Odd Binary Number

Easy83.0% acceptance3 companies

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'.

Asked at 3 companies

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

The binary representation of an odd number contains '1' in the least significant place.

9:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumOddBinaryNumber(self, s: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"010"

Input

"0101"

Your code is saved on this device.Solution