Maximum Odd Binary Number

Easy
568.

Maximum Odd Binary Number

Maximum Odd Binary Number is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.

You are given a binary string s containing at least one '1'.

Rearrange its bits to form the maximum odd binary number possible. The result may have leading zeros. Return it as a string.

Example 1

Input
s = "010"
Output
001
Explanation
There is only one 1, and it must be the last bit for the number to be odd.

Example 2

Input
s = "0101"
Output
1001
Explanation
One 1 goes last; the other goes as far left as possible.

Example 3

Input
s = "111"
Output
111

Constraints

  • 1 <= s.length <= 100
  • s consists only of '0' and '1'.
  • s contains at least one '1'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var maximumOddBinaryNumber = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Odd Binary Number — Solution in Python, Java & C++

Maximum Odd Binary Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Odd Binary Number is an easy coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary string s containing at least one '1'.

Rearrange its bits to form the maximum odd binary number possible. The result may have leading zeros. Return it as a string.

Example 1

Input: s = "010"
Output: 001
Explanation: There is only one 1, and it must be the last bit for the number to be odd.

Example 2

Input: s = "0101"
Output: 1001
Explanation: One 1 goes last; the other goes as far left as possible.

Example 3

Input: s = "111"
Output: 111

Constraints

  • 1 <= s.length <= 100
  • s consists only of '0' and '1'.
  • s contains at least one '1'.

Hints for Maximum Odd Binary Number

  1. Hint 1

    Odd means the last bit must be a 1 — that consumes one of them.

  2. Hint 2

    To maximise the value, push every remaining 1 as far left as possible.

  3. Hint 3

    So the answer is (ones - 1) ones, then all the zeros, then a final 1.

How to solve Maximum Odd Binary Number

Parity fixes the last bit; maximisation fixes everything else. Reserve one 1 for the units place and put the rest at the front.

Approach

  1. Count the ones; the zeros are the rest.
  2. Emit ones - 1 ones, then every zero, then a single trailing 1.

Why it works

Any odd arrangement must end in 1. Among those, value is maximised by placing the remaining ones in the most significant positions available — which is exactly a block of ones followed by a block of zeros.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Sorting descending gives the maximum number but usually an even one.
  • With exactly one 1, ones - 1 is 0 and the answer is all zeros followed by that 1.
  • The result keeps the original length, leading zeros included.

Reference solution

Python

def maximumOddBinaryNumber(s: str) -> str:
    ones = s.count('1')
    zeros = len(s) - ones
    return '1' * (ones - 1) + '0' * zeros + '1'

Java

public static String maximumOddBinaryNumber(String s) {
    int ones = 0;
    for (int i = 0; i < s.length(); i++) if (s.charAt(i) == '1') ones++;
    int zeros = s.length() - ones;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < ones - 1; i++) sb.append('1');
    for (int i = 0; i < zeros; i++) sb.append('0');
    sb.append('1');
    return sb.toString();
}

C++

string maximumOddBinaryNumber(string s) {
    int ones = 0;
    for (char c : s) if (c == '1') ones++;
    int zeros = (int) s.size() - ones;
    return string(ones - 1, '1') + string(zeros, '0') + "1";
}

JavaScript

var maximumOddBinaryNumber = function(s) {
    let ones = 0;
    for (let i = 0; i < s.length; i++) if (s.charAt(i) === "1") ones++;
    const zeros = s.length - ones;
    let out = "";
    for (let i = 0; i < ones - 1; i++) out += "1";
    for (let i = 0; i < zeros; i++) out += "0";
    return out + "1";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms