Maximum Odd Binary Number

easy greedy string binary

Problem

You are given a binary string s containing at least one '1'. Rearrange its bits to form the maximum odd binary number possible. A binary number is odd only when its least significant (last) bit is '1', so exactly one '1' must sit at the end; to maximize the value, push every other '1' as far left as possible. Leading zeros are allowed.

Inputs = "0101"

Output"1001"

Two '1's: one is reserved for the last slot. The other '1' goes first, the two '0's fill the middle → "1001".

s (binary string with at least one '1')

def maximumOddBinaryNumber(s):
    ones = s.count("1")          # how many 1-bits we have
    zeros = len(s) - ones        # the rest are 0-bits
    # Greedy layout: (ones-1) leading 1s, then all 0s,
    # then a single trailing 1 to make the number odd.
    return "1" * (ones - 1) + "0" * zeros + "1"

function maximumOddBinaryNumber(s) {
  let ones = 0;
  for (const ch of s) if (ch === "1") ones++;   // count 1-bits
  const zeros = s.length - ones;                 // the rest are 0s
  // (ones-1) leading 1s, all 0s, then one trailing 1 (odd).
  return "1".repeat(ones - 1) + "0".repeat(zeros) + "1";
}

String maximumOddBinaryNumber(String s) {
    int ones = 0;
    for (char ch : s.toCharArray()) if (ch == '1') ones++; // count 1s
    int zeros = s.length() - ones;                         // rest are 0s
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < ones - 1; i++) sb.append('1'); // leading 1s
    for (int i = 0; i < zeros; i++) sb.append('0');    // middle 0s
    sb.append('1');                                     // trailing 1 (odd)
    return sb.toString();
}

string maximumOddBinaryNumber(string s) {
    int ones = count(s.begin(), s.end(), '1'); // count 1-bits
    int zeros = s.size() - ones;               // rest are 0s
    // (ones-1) leading 1s, all 0s, then one trailing 1 (odd).
    return string(ones - 1, '1') + string(zeros, '0') + "1";
}

Explanation

This is a greedy counting problem. We never have to try different arrangements — a single pass to tally the bits tells us exactly where everything belongs.

First, recall what makes a binary number odd: its last (least significant) bit must be '1'. Since the answer must be odd, we are forced to reserve one '1' for the final position. That choice is non-negotiable.

To make the number as large as possible, the most significant bits should be '1' and the bigger weights should be filled first. So we greedily place every remaining '1' (there are ones − 1 of them) at the very front, then all the '0's, and finally the one reserved '1' at the end.

So the whole solution is: count the ones, and emit "1"×(ones−1) + "0"×zeros + "1". No comparisons, no sorting — just counting.

Example: s = "0101" has two '1's and two '0's. Reserve one '1' for the end, put the other '1' first, drop the two '0's in the middle → "1001", which is the largest odd value those bits can form.

Time: O(n) Space: O(n)