Jobs

Interviews

Discussions

Maximum Odd Binary Number

Easy

Asked by:

12 views

Topics:

StringsGreedy Algorithms

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.

Example 1:

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Example 2:

Input: s = "0101"
Output: "1001"
Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".

Constraints:

1 <= s.length <= 100
s consists only of '0' and '1'.
s contains at least one '1'.

Maximum Odd Binary Number

Easy

Asked by:

12 views

Topics:

StringsGreedy Algorithms

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.

Example 1:

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Example 2:

Input: s = "0101"
Output: "1001"
Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".

Constraints:

1 <= s.length <= 100
s consists only of '0' and '1'.
s contains at least one '1'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string s?
Is the input string s guaranteed to contain at least one '1'?
If the input string is empty, what should I return?
Are there any invalid characters besides '0' and '1' that I need to handle, or can I assume the input is always a valid binary string?
If there are multiple possible maximum odd binary numbers after rearrangement, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force method involves generating every possible combination of a binary number with the given number of digits, then checking if each combination is both odd and the largest one we've seen so far. This approach explores every single possibility to guarantee finding the correct answer.

Here's how the algorithm would work step-by-step:

Start by listing out every single possible binary number that can be made using the amount of digits given.
For each binary number, check to see if it is odd.
If the number is odd, check to see if it is bigger than the largest odd number we have seen so far.
If it is bigger, remember this number as the current largest odd number.
After checking every possible binary number, the largest odd number we remembered will be the answer.

Code Implementation

def maximum_odd_binary_number_brute_force(binary_string):
    string_length = len(binary_string)
    largest_odd_binary_number = ""

    # Iterate through all possible binary numbers of given length
    for i in range(2**string_length):
        binary_representation = bin(i)[2:].zfill(string_length)

        # Check if the binary representation is odd
        if int(binary_representation[-1]) == 1:

            # This ensures we only compare odd binary numbers.

            if largest_odd_binary_number == "" or int(binary_representation, 2) > int(largest_odd_binary_number, 2):

                # Need to check if it's the largest seen so far.

                largest_odd_binary_number = binary_representation

    return largest_odd_binary_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm generates all possible binary numbers of length n. Generating all combinations of n digits where each digit can be 0 or 1 requires examining 2^n possibilities. For each of these 2^n binary numbers, we perform a check to determine if it is odd. The comparison to find the maximum odd number found so far takes constant time per comparison. Therefore, the dominant factor is the generation and examination of 2^n binary numbers, leading to a time complexity of O(2^n).

Space Complexity

O(1) – The brute force approach generates every possible binary number and checks each one. Although it iterates through many numbers, it only stores one candidate for the largest odd number seen so far. The memory used to store this single largest odd number is constant, regardless of N (the number of digits). Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to rearrange the binary string such that it represents the largest possible odd number. We achieve this by strategically placing the '1's and '0's to maximize the value.

Here's how the algorithm would work step-by-step:

Count how many '1's there are in the binary string.
Reduce the count of '1's by one because one '1' needs to be at the very end to make the number odd.
Create a new string that starts with the remaining number of '1's.
Fill the rest of the string with '0's.
Finally, add the single '1' to the very end of the string.

Code Implementation

def maximum_odd_binary_number(binary_string):
    ones_count = 0
    for bit in binary_string:
        if bit == '1':
            ones_count += 1

    # One '1' is reserved for the last position to make it odd.
    ones_count -= 1

    # Build the string with remaining ones followed by zeros.
    result = ''
    for _ in range(ones_count):
        result += '1'

    zeros_count = len(binary_string) - (ones_count + 1)

    # Pad the result string with zeros.
    for _ in range(zeros_count):
        result += '0'

    # Append '1' to the end to ensure the number is odd
    result += '1'

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the length of the binary string, which we denote as n. Step 1 involves counting the number of '1's, requiring a single pass through the string. Step 3 and 4 involve creating a new string which takes O(n) time. Step 2 and 5 take constant time. Therefore, the overall time complexity is dominated by the initial count and string creation, both being linear with respect to the input size, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a new string to store the rearranged binary number. The size of this new string is directly dependent on the length of the input binary string, N. The space required for this new string grows linearly with the input size N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately since there's nothing to rearrange.
Input string with only zeros	Return an empty string because it's impossible to form an odd number.
Input string with only ones	Return the original string with one '1' moved to the end to ensure oddness.
Input string with a single character ('0' or '1')	If it's '0', return empty string; if it's '1', return the string '1'.
Input string with a large number of characters (performance)	The solution should have O(n) time complexity where n is the string length, usually by counting ones and zeros.
Input string with a high skew towards '0's and few '1's	The algorithm should correctly place all the '0's before the last '1'.
Input string with a high skew towards '1's and few '0's	The algorithm correctly places as many ones as possible at the beginning before the zeros, ensuring exactly one 1 remains at the end.
Integer overflow when counting the number of 1s	Use appropriate data types to prevent integer overflow when counting the number of 1s (e.g., long).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the binary string s?
Is the input string s guaranteed to contain at least one '1'?
If the input string is empty, what should I return?
Are there any invalid characters besides '0' and '1' that I need to handle, or can I assume the input is always a valid binary string?
If there are multiple possible maximum odd binary numbers after rearrangement, is any valid solution acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by listing out every single possible binary number that can be made using the amount of digits given.
For each binary number, check to see if it is odd.
If the number is odd, check to see if it is bigger than the largest odd number we have seen so far.
If it is bigger, remember this number as the current largest odd number.
After checking every possible binary number, the largest odd number we remembered will be the answer.

Code Implementation

def maximum_odd_binary_number_brute_force(binary_string):
    string_length = len(binary_string)
    largest_odd_binary_number = ""

    # Iterate through all possible binary numbers of given length
    for i in range(2**string_length):
        binary_representation = bin(i)[2:].zfill(string_length)

        # Check if the binary representation is odd
        if int(binary_representation[-1]) == 1:

            # This ensures we only compare odd binary numbers.

            if largest_odd_binary_number == "" or int(binary_representation, 2) > int(largest_odd_binary_number, 2):

                # Need to check if it's the largest seen so far.

                largest_odd_binary_number = binary_representation

    return largest_odd_binary_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to rearrange the binary string such that it represents the largest possible odd number. We achieve this by strategically placing the '1's and '0's to maximize the value.

Here's how the algorithm would work step-by-step:

Count how many '1's there are in the binary string.
Reduce the count of '1's by one because one '1' needs to be at the very end to make the number odd.
Create a new string that starts with the remaining number of '1's.
Fill the rest of the string with '0's.
Finally, add the single '1' to the very end of the string.

Code Implementation

def maximum_odd_binary_number(binary_string):
    ones_count = 0
    for bit in binary_string:
        if bit == '1':
            ones_count += 1

    # One '1' is reserved for the last position to make it odd.
    ones_count -= 1

    # Build the string with remaining ones followed by zeros.
    result = ''
    for _ in range(ones_count):
        result += '1'

    zeros_count = len(binary_string) - (ones_count + 1)

    # Pad the result string with zeros.
    for _ in range(zeros_count):
        result += '0'

    # Append '1' to the end to ensure the number is odd
    result += '1'

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately since there's nothing to rearrange.
Input string with only zeros	Return an empty string because it's impossible to form an odd number.
Input string with only ones	Return the original string with one '1' moved to the end to ensure oddness.
Input string with a single character ('0' or '1')	If it's '0', return empty string; if it's '1', return the string '1'.
Input string with a large number of characters (performance)	The solution should have O(n) time complexity where n is the string length, usually by counting ones and zeros.
Input string with a high skew towards '0's and few '1's	The algorithm should correctly place all the '0's before the last '1'.
Input string with a high skew towards '1's and few '0's	The algorithm correctly places as many ones as possible at the beginning before the zeros, ensuring exactly one 1 remains at the end.
Integer overflow when counting the number of 1s	Use appropriate data types to prevent integer overflow when counting the number of 1s (e.g., long).