Problem Description

You have an array nums containing exactly 3 integers.

Your task is to find the maximum possible number that can be created by:

1. Converting each integer in nums to its binary representation (without leading zeros)
2. Concatenating these binary representations in some order
3. Converting the resulting binary string back to a decimal number

For example, if you have numbers like 1, 2, and 3:

• 1 in binary is "1"
• 2 in binary is "10"
• 3 in binary is "11"

You can arrange these binary strings in different orders like "11011" (from 1,10,11) or "11110" (from 11,1,10) or "10111" (from 10,1,11), etc. Each arrangement gives a different decimal value when converted back.

The solution works by trying all 6 possible permutations of the 3 numbers (since 3! = 6). For each permutation:

• Convert each number to its binary string using bin(i)[2:] (the [2:] removes the '0b' prefix)
• Join all binary strings together
• Convert the concatenated binary string to decimal using int(..., 2)
• Track the maximum value found

The function returns the largest decimal number that can be formed through any arrangement of the binary representations.

Intuition

When we concatenate binary strings, we want the resulting binary number to be as large as possible. In binary, a number is larger when it has more significant bits set to 1 in the leftmost positions.

Since we're dealing with only 3 numbers, the brute force approach becomes feasible. With just 3 elements, there are only 3! = 6 possible arrangements to check. This small number of possibilities makes it practical to simply try all permutations and pick the maximum.

The key insight is that the optimal ordering isn't immediately obvious from just looking at the decimal values. For instance, if we have numbers 2 ("10"), 8 ("1000"), and 10 ("1010"), the arrangement that produces the maximum isn't necessarily in descending order of the original numbers. We need to consider how the binary representations concatenate together.

When we concatenate "10" + "1000" we get "101000" (which is 40 in decimal), but if we concatenate "1000" + "10" we get "100010" (which is 34 in decimal). The first arrangement is better even though we put the smaller number first.

Since determining the optimal order requires considering the actual binary concatenations and there's no simple rule to determine the best order without trying the combinations, the most straightforward approach is to generate all permutations, compute the resulting decimal value for each, and return the maximum. The small fixed size of the input (always 3 elements) makes this exhaustive search both simple and efficient.

Solution Approach

The solution uses a brute force enumeration approach with Python's permutations function from the itertools module.

Step-by-step implementation:

1. Initialize the maximum value: Start with ans = 0 to track the maximum decimal number found.

2. Generate all permutations: Use permutations(nums) to generate all 6 possible orderings of the 3 numbers. For example, if nums = [1, 2, 3], it generates:

   • (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

3. Process each permutation: For each arrangement arr:

   • Convert each number to binary using bin(i)[2:]
     • bin(i) returns a string like "0b101"
     • [2:] slices off the "0b" prefix, leaving just "101"
   • Join all binary strings together using "".join(...)
   • Convert the concatenated binary string to decimal using int(..., 2) where the second parameter 2 indicates base-2 (binary)

4. Track the maximum: Compare each resulting decimal number with the current maximum using ans = max(ans, num).

5. Return the result: After checking all permutations, return the maximum value found.

Example walkthrough:

If nums = [1, 2, 3]:

• Permutation (1, 2, 3): "1" + "10" + "11" = "11011" → 27 in decimal
• Permutation (3, 2, 1): "11" + "10" + "1" = "11101" → 29 in decimal
• And so on for all 6 permutations...

The algorithm would return 30, which comes from the arrangement that produces "11110" in binary.

The time complexity is O(1) since we always have exactly 3 elements and 6 permutations to check. The space complexity is also O(1) as we only store a fixed amount of data regardless of the input values.

Example Walkthrough

Let's walk through the solution with nums = [2, 8, 10]:

Step 1: Convert each number to binary

• 2 → "10"
• 8 → "1000"
• 10 → "1010"

Step 2: Try all 6 permutations and calculate their decimal values

1. (2, 8, 10): "10" + "1000" + "1010" = "1010001010"

   • Converting "1010001010" to decimal: 650

2. (2, 10, 8): "10" + "1010" + "1000" = "1010101000"

   • Converting "1010101000" to decimal: 680

3. (8, 2, 10): "1000" + "10" + "1010" = "1000101010"

   • Converting "1000101010" to decimal: 554

4. (8, 10, 2): "1000" + "1010" + "10" = "100010101"0

   • Converting "10001010010" to decimal: 1106

5. (10, 2, 8): "1010" + "10" + "1000" = "1010101000"

   • Converting "1010101000" to decimal: 680

6. (10, 8, 2): "1010" + "1000" + "10" = "101010001"0

   • Converting "10101000010" to decimal: 1346

Step 3: Find the maximum Comparing all results: 650, 680, 554, 1106, 680, 1346

The maximum value is 1346, which comes from the arrangement (10, 8, 2).

This demonstrates why we need to check all permutations - the optimal order isn't intuitive and doesn't follow the original decimal ordering of the numbers.

Solution Implementation

Time and Space Complexity

The time complexity is O(n! × n × log M), where n is the length of the nums array (which is 3 based on the problem context) and M represents the maximum value of the elements in nums. Breaking this down:

• permutations(nums) generates n! permutations
• For each permutation, we iterate through n elements to build the binary string
• Converting each number to binary using bin(i)[2:] takes O(log M) time
• The int(..., 2) conversion also takes O(n × log M) time for the concatenated binary string

Since n = 3 is a constant, the time complexity simplifies to O(log M).

The space complexity is O(n × log M) for storing the concatenated binary string during each iteration. However, since n = 3 is constant and we're not storing all permutations simultaneously, the space complexity simplifies to O(log M). If we consider only the extra space beyond the input, it can be considered O(1) when treating the maximum binary representation length as a constant factor.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. String Concatenation Order Confusion

A common mistake is assuming that lexicographically larger binary strings will always produce larger decimal values when concatenated. This isn't true because the position of bits matters significantly in the final decimal value.

Incorrect Assumption:

# Wrong: Trying to sort binary strings lexicographically
def maxGoodNumber(self, nums: List[int]) -> int:
    binaries = [bin(num)[2:] for num in nums]
    binaries.sort(reverse=True)  # This doesn't guarantee maximum decimal
    return int("".join(binaries), 2)

Why it fails: Consider nums = [1, 2, 3]:

• Sorting binary strings: ["11", "10", "1"] → "11101" = 29
• But ["11", "1", "10"] → "11110" = 30 (which is larger!)

2. Custom Comparator Pitfall

Another flawed approach is using a custom comparator to sort numbers based on their concatenated binary values:

Incorrect Implementation:

# Wrong: Simple comparison of concatenated pairs
def maxGoodNumber(self, nums: List[int]) -> int:
    nums.sort(key=lambda x: bin(x)[2:], reverse=True)
    binary = "".join(bin(num)[2:] for num in nums)
    return int(binary, 2)

Correct Approach with Custom Comparator:

from functools import cmp_to_key

def maxGoodNumber(self, nums: List[int]) -> int:
    def compare(x, y):
        # Compare which order produces a larger binary number
        bin_x, bin_y = bin(x)[2:], bin(y)[2:]
        if bin_x + bin_y > bin_y + bin_x:
            return -1  # x should come before y
        elif bin_x + bin_y < bin_y + bin_x:
            return 1   # y should come before x
        else:
            return 0   # order doesn't matter
  
    nums.sort(key=cmp_to_key(compare))
    binary_string = "".join(bin(num)[2:] for num in nums)
    return int(binary_string, 2)

3. Overlooking Edge Cases with Zero

If the array contains 0, its binary representation is just "0", which acts as padding when placed in the middle or beginning:

Example: nums = [0, 1, 2]

• [1, 2, 0] → "1" + "10" + "0" = "1100" = 12
• [2, 1, 0] → "10" + "1" + "0" = "1010" = 10
• Always place zeros at the end for maximum value!

4. Integer Overflow Concerns

While Python handles arbitrary precision integers automatically, in other languages you might encounter overflow:

Prevention Strategy:

• Check the maximum possible binary string length: with 3 numbers each up to 10^9, the binary representation can be quite long
• In languages like Java or C++, use appropriate data types (long long in C++, Long in Java)
• Consider using string comparison if the result might exceed integer limits

Example validation:

def maxGoodNumber(self, nums: List[int]) -> int:
    max_value = 0
  
    for permutation in permutations(nums):
        binary_string = "".join(bin(num)[2:] for num in permutation)
      
        # Optional: Check for potential overflow in other languages
        if len(binary_string) > 64:  # Would overflow in 64-bit systems
            # Handle appropriately based on requirements
            pass
      
        decimal_value = int(binary_string, 2)
        max_value = max(max_value, decimal_value)
  
    return max_value