# Maximum Odd Binary Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-odd-binary-number)
Canonical: https://scaleengineer.com/dsa/problems/maximum-odd-binary-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
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'`.

# Approaches
## Sorting Approach
This approach involves sorting the characters of the string to group the '1's and '0's. By sorting in descending order, we get the largest possible binary number. A final swap is needed to ensure the number is odd.
**Time:** O(N log N), where N is the length of the string. The performance is dominated by the sorting operation. · **Space:** O(N), to store the character array. In Java, strings are immutable, so creating a character array for sorting is necessary.
**Pros:** Relatively straightforward to conceptualize if one thinks of rearranging bits as a sorting problem.
**Cons:** Sub-optimal time complexity compared to linear-time solutions.; The logic for the final swap can be slightly more complex than a direct construction method.
### Explanation
The core idea is that the largest binary number is formed by placing as many '1's as possible in the most significant (leftmost) positions. Sorting the binary string in descending order achieves this, resulting in a string like `11...100...0`. However, this number is even (unless it contains no '0's). To make it odd, the last digit must be '1'. Since the input is guaranteed to have at least one '1', we can always make an odd number. The algorithm first sorts the characters in descending order and then performs a swap to move one '1' to the end, thus satisfying both conditions of being maximum and odd.

```java
import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String maximumOddBinaryNumber(String s) {
        int n = s.length();
        Character[] chars = new Character[n];
        for (int i = 0; i < n; i++) {
            chars[i] = s.charAt(i);
        }

        // Sort in descending order ('1's first, then '0's)
        Arrays.sort(chars, Collections.reverseOrder());

        // Find the last '1' and swap it with the last element
        // to make the number odd.
        for (int i = n - 1; i >= 0; i--) {
            if (chars[i] == '1') {
                // Swap chars[i] with the last element
                char temp = chars[i];
                chars[i] = chars[n - 1];
                chars[n - 1] = temp;
                break;
            }
        }

        StringBuilder result = new StringBuilder(n);
        for (char c : chars) {
            result.append(c);
        }
        return result.toString();
    }
}
```
### Algorithm
*   Convert the input string `s` into a character array `chars`.
*   Sort `chars` in descending order. For characters, this means '1' comes before '0'.
*   Find the index of the last '1' in the sorted array.
*   Swap the character at this index with the character at the last position of the array (`s.length() - 1`).
*   Convert the modified character array back to a string.

## Counting and String Construction
This is a highly efficient and straightforward approach. It relies on the logical construction of the target number based on the properties of maximum and odd binary numbers. We simply count the occurrences of '1's and '0's and then build the result string directly according to the derived optimal structure.
**Time:** O(N), where N is the length of the string. We perform a single pass to count the characters and another effective pass to construct the result string. · **Space:** O(N), to store the `StringBuilder` and the final result string. This is optimal as a new string of length N must be returned.
**Pros:** Optimal time complexity of O(N).; Simple and direct logic, making it easy to implement and less prone to errors.
**Cons:** Requires extra space to build the new string, although this is generally unavoidable for languages with immutable strings.
### Explanation
To form the maximum odd binary number, we must satisfy two conditions:
1.  The number must be odd, which requires its last bit to be '1'.
2.  The number must be as large as possible, which means the remaining '1's should be placed at the most significant (leftmost) positions.

This leads to a simple structure for the result: `(all other '1's) + (all '0's) + (one '1')`. The algorithm implements this construction directly.

```java
class Solution {
    public String maximumOddBinaryNumber(String s) {
        int onesCount = 0;
        int n = s.length();
        for (char c : s.toCharArray()) {
            if (c == '1') {
                onesCount++;
            }
        }
        int zerosCount = n - onesCount;

        StringBuilder result = new StringBuilder();

        // 1. Append all '1's except one for the most significant part
        for (int i = 0; i < onesCount - 1; i++) {
            result.append('1');
        }

        // 2. Append all '0's for the middle part
        for (int i = 0; i < zerosCount; i++) {
            result.append('0');
        }

        // 3. Append the last '1' to make the number odd
        result.append('1');

        return result.toString();
    }
}
```
### Algorithm
*   Iterate through the input string `s` to count the total number of '1's (`onesCount`).
*   The number of '0's is `s.length() - onesCount`.
*   Initialize a `StringBuilder` to build the result.
*   Append `onesCount - 1` characters of '1' to the builder.
*   Append `zerosCount` characters of '0' to the builder.
*   Append a single '1' to the builder.
*   Convert the `StringBuilder` to a string and return it.

# Solutions
### Python

```python
class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str: cnt = s . count("1") return "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"

```

### Java

```java
class Solution {
public
  String maximumOddBinaryNumber(String s) {
    int cnt = 0;
    for (char c : s.toCharArray()) {
      if (c == '1') {
        ++cnt;
      }
    }
    return "1".repeat(cnt - 1) + "0".repeat(s.length() - cnt) + "1";
  }
}

```

### CPP

```cpp
class Solution {
public:
  string maximumOddBinaryNumber(string s) {
    int cnt = count_if(s.begin(), s.end(), [](char c) { return c == '1'; });
    string ans;
    for (int i = 1; i < cnt; ++i) {
      ans.push_back('1');
    }
    for (int i = 0; i < s.size() - cnt; ++i) {
      ans.push_back('0');
    }
    ans.push_back('1');
    return ans;
  }
};

```