algoadvance

Leetcode 2864. Maximum Odd Binary Number

Problem Statement

You are given a binary string s (possibly with leading zeros), which represents a binary number. Your task is to rearrange the bits in the string to get the maximum odd binary number possible. The output should also be a binary string. A binary number is odd if its last digit is 1.

Example:

  1. Input: s = "010" Output: s = "100"
  2. Input: s = "1011" Output: s = "1110"

Clarifying Questions

  1. Can the string s be empty?
    • No, it is guaranteed that the string s will have at least one character.
  2. What characters can be in the string s?
    • The string s will only contain ‘0’ and ‘1’ characters.
  3. Is there an upper limit on the length of the string s?
    • The problem does not specify an upper limit. Assume it can be reasonably large within practical execution constraints.
  4. Should the output retain any specific formatting?
    • The output should be a binary string which represents the maximum odd number obtainable by rearranging the bits.

Strategy

  1. Count the number of 0s and 1s in the string: Determine the frequency of 0s and 1s in the string s.
  2. Formulate the binary string:
    • The largest binary number has the most significant bit as 1. Hence, we need to keep as many 1s as possible at the most significant positions.
    • To ensure the number is odd, the least significant bit should be 1.
  3. Construct the result string:
    • Place all remaining 1s at the beginning (except one which will be placed at the end to ensure odd number).
    • Place all 0s next.
    • End the string with a single 1 to ensure the number is odd.

Code

public class MaximumOddBinaryNumber {
    public static String maximumOddBinaryNumber(String s) {
        int count1s = 0;
        int count0s = 0;
        
        for(char c : s.toCharArray()) {
            if (c == '1') {
                count1s++;
            } else {
                count0s++;
            }
        }
        
        if (count1s == 0) {
            return "0"; // No way to get an odd number, default to "0" (though constraints guarantee at least one character).
        }
        
        StringBuilder result = new StringBuilder();
        
        // Add all but one '1' at the start
        for (int i = 0; i < count1s - 1; i++) {
            result.append('1');
        }
        
        // Add all '0's
        for (int i = 0; i < count0s; i++) {
            result.append('0');
        }
        
        // Finally, add the last '1' to make the number odd
        result.append('1');
        
        return result.toString();
    }

    public static void main(String[] args) {
        String s1 = "010";
        System.out.println(maximumOddBinaryNumber(s1)); // Output: "100"
        
        String s2 = "1011";
        System.out.println(maximumOddBinaryNumber(s2)); // Output: "1110"
    }
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the string s. This complexity arises from:

This approach ensures that the solution is efficient and works within the constraints of the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI