💬 Discord
Sign In
NeetCode #765LC-2864EasyGreedy
← Back to All Problems

#765 · #2864 · Maximum Odd Binary Number(最大二进制奇数)

📌 Problem Statement & Constraints

You are given a binary string s containing at least one 1. Rearrange its bits to form the maximum odd binary number (a binary string with no leading zeros). Constraints: 1 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. A binary number is odd iff its last bit is 1, so reserve one 1 for the end.
  2. To maximise the value, place all remaining 1 bits at the front (the most significant positions).
  3. Then place all 0 bits, and finish with the reserved 1.
  4. This yields the shape 1...10...01.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): counting the bits plus building the result.
💾 Space Complexity
O(n): the output string.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the trailing 1: without it the number is even and the result is wrong.
  • Placing a 0 at the front: the result must have no leading zeros, so the leading positions are all 1.
  • Assuming the string already has a fixed length: the length is preserved by rearranging, and the counts add up.
  • Using ones - 1 when ones == 0: the constraint guarantees at least one 1, so this is safe.