Leetcode 2864: Maximum Odd Binary Number

Input: The input consists of a binary string s containing only '0' and '1' characters. The string will contain at least one '1'.

Example: s = "100"

Constraints:

• 1 <= s.length <= 100

• s contains only '0' and '1'.

• s contains at least one '1'.

Output: Return a string representing the largest odd binary number that can be created from the given binary string.

Example: For input s = "100", the output is "010".

Constraints:

Goal: The goal is to rearrange the bits in such a way that the resulting binary number is the largest odd binary number possible.

Steps:

• Identify and place the '1' in the last position to ensure the binary number is odd.

• Sort the remaining bits in descending order to form the largest possible binary number.

Goal: The problem requires a rearrangement of the bits while keeping the last bit '1' to ensure the binary number is odd.

Steps:

• 1 <= s.length <= 100

• The string contains at least one '1'.

Assumptions:

• The binary string contains at least one '1', ensuring that a valid odd binary number can be created.

• Input: For input s = "100", the output is "010".

• Explanation: To create the largest odd binary number, the '1' must be placed in the last position. The remaining bits '10' can be rearranged as "01", resulting in the binary number "010".

Approach: The approach involves rearranging the bits of the binary string to maximize the resulting odd binary number by ensuring the last bit is '1' and sorting the remaining bits in descending order.

Observations:

• The last bit must always be '1' for the binary number to be odd.

• The remaining bits should be sorted to form the largest possible number.

• If the binary string has more than one '1', we need to place one '1' at the end and arrange the rest of the bits in descending order.

Steps:

• Find all the '1's and move one to the last position.

• Sort the remaining bits (the '1's and '0's) in descending order to form the largest binary number.

Empty Inputs:

• The input string is guaranteed to contain at least one '1', so no need to handle empty inputs.

Large Inputs:

• The solution must handle input strings of length up to 100 characters efficiently.

Special Values:

• If the string already ends with '1', only sorting the remaining bits is necessary.

Constraints:

• The algorithm must ensure that the result is the largest odd binary number possible.

string maximumOddBinaryNumber(string s) {
int i = 0, sz = s.size();
for(int j = 0;j < sz - 1; ++j) {
    if(s[j] == '1') {
        swap(s[j], s[i]);
        ++i;
    } 
}

if(s.back() != '1') 
    swap(s[sz - 1], s[i - 1]);
return s;
}

1 : Function Start

string maximumOddBinaryNumber(string s) {

Start of the function definition for maximumOddBinaryNumber.

2 : Variable Initialization

int i = 0, sz = s.size();

Initialize index 'i' to 0 and calculate the size of the string 's'.

3 : Loop Start

for(int j = 0;j < sz - 1; ++j) {

Start a loop that iterates over each character of the string, except the last one.

4 : Condition Check

    if(s[j] == '1') {

Check if the current character at position 'j' is '1'.

5 : Swap Operation

        swap(s[j], s[i]);

If the current character is '1', swap it with the character at index 'i'.

6 : Increment Index

        ++i;

Increment the index 'i' after swapping.

7 : Condition Check for Last Character

if(s.back() != '1')

Check if the last character of the string is not '1'.

8 : Final Swap

    swap(s[sz - 1], s[i - 1]);

If the last character is not '1', swap it with the character at index 'i - 1'.

9 : Return Statement

return s;

Return the modified string which now represents the maximum odd binary number.

Best Case: O(n log n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: Sorting the bits requires O(n log n) time where n is the length of the string.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the need for sorting the string.

Leetcode 2864: Maximum Odd Binary Number

Explore →