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 <= 100s consists only of '0' and '1'.s contains at least one '1'.
Hints for Maximum Odd Binary Number
Hint 1
Odd means the last bit must be a 1 — that consumes one of them.
Hint 2
To maximise the value, push every remaining 1 as far left as possible.
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
- Count the ones; the zeros are the rest.
- Emit
ones - 1ones, 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 - 1is 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