Teaching Kids Programming – Maximum Odd Binary Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Algorithm to Compute the Maximum Odd Binary Number

We can count the number of “1”s and “0”s in the binary string. And we leave one in the LSB (Least Significant Bit) to make it odd number, and then we put the remaining “1”s as left as possible (Most Significant Bits), and the remaining “0”s on the right (before the LSB “1” we just put)

We use the Counter aka Hash Map to store the frequencies of “1”s and “0”s.

1
2
3
4
5

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        c = Counter(s)
        n = c['1']
        return (n - 1) * '1' + c['0'] * '0' + '1'

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        c = Counter(s)
        n = c['1']
        return (n - 1) * '1' + c['0'] * '0' + '1'

–EOF (The Ultimate Computing & Technology Blog) —