We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Odd Binary Number

Difficulty: Easy

Problem Description

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.

Key Insights

  • The binary number is odd if it ends with '1'.
  • To maximize the binary number, we should have as many '1's as possible on the left side of the string.
  • The last digit must be '1' to ensure the number is odd.
  • The remaining '1's should be placed before the last '1', followed by all '0's.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s.
Space Complexity: O(n), for storing the result string.

Solution

We can solve the problem by following these steps:

  1. Count the number of '1's and '0's in the string s.
  2. Ensure that one '1' is placed at the end to maintain the odd property.
  3. Place the remaining '1's at the start followed by all the '0's.
  4. Construct the final string and return it.

The approach uses simple counting and string manipulation.

Code Solutions

def maximumOddBinaryNumber(s: str) -> str:
    count1 = s.count('1')  # Count number of '1's
    count0 = s.count('0')  # Count number of '0's
    # Create the maximum odd binary number
    return '1' * count1 + '0' * count0[:-1] + '1'  # Last '1' to ensure it's odd
← Back to All Questions