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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Odd Binary Number

Number: 3055

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given a binary string s that contains at least one '1', rearrange its bits to form the maximum odd binary number possible. The resulting number may have leading zeros.

Key Insights

  • The binary number must be odd, which means its last digit must be '1'.
  • To maximize the binary number, we want as many '1's as possible in the most significant (leftmost) positions.
  • Reserve one '1' for the last position to ensure the number is odd.
  • The remaining bits can be optimally arranged by placing all remaining '1's first (to maximize value) followed by all '0's.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (we just count characters and build the result). Space Complexity: O(n), for constructing the output string.

Solution

Count the number of ones and zeros in the given binary string. Reserve one '1' to be placed at the end to guarantee the number is odd. Then, place all the remaining ones at the beginning (to ensure maximum significance), followed by all zeros. Finally, append the reserved '1' at the end. This arrangement guarantees the maximum odd binary number because higher-order positions get the '1's which contribute more to the binary value.

Code Solutions

# Define the function to compute the maximum odd binary number.
def maximumOddBinaryNumber(s: str) -> str:
    # Count the number of '1's in the string.
    count_ones = s.count('1')
    # Count the number of '0's in the string.
    count_zeros = s.count('0')
    
    # Reserve one '1' for the last digit to make the number odd.
    # The remaining ones will be placed in the left most positions.
    # If there is only one '1', it will become the last digit.
    result = '1' * (count_ones - 1) + '0' * count_zeros + '1'
    return result

# Example usage:
if __name__ == "__main__":
    s1 = "010"
    s2 = "0101"
    print(maximumOddBinaryNumber(s1))  # Expected output: "001"
    print(maximumOddBinaryNumber(s2))  # Expected output: "1001"
← Back to All Questions