LeetCode 3309 - Maximum Possible Number by Binary Concatenation

LeetCode Problem 3309

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem is asking for the maximum integer value that can be created by concatenating the binary representations of all elements in a list of three integers. Each number should be converted to its binary representation without leading zeros. After conversion, the binary strings can be concatenated in any order. The resulting binary string should then be interpreted as a decimal integer, which is the final output.

The input nums is guaranteed to have exactly three integers, each between 1 and 127. This ensures that each binary representation fits within 7 bits, and there will never be any leading zeros in the binary conversion.

The output is a single integer that is the maximum possible value formed by any ordering of the binary strings. Edge cases include numbers that have binary representations of different lengths, as the position of longer binary strings can disproportionately increase the final integer value.

Approaches

The brute-force approach involves generating all possible permutations of the three integers, converting each to binary, concatenating them, and then converting the concatenation back to an integer. This guarantees correctness because it exhaustively checks all orderings, but it is unnecessary for such a small fixed input because there is a mathematical way to choose the "largest" concatenation directly.

The key insight for an optimal solution is that the ordering of binary strings is similar to string sorting for maximum concatenation, where for any two binary strings a and b, placing a before b is better if a+b is lexicographically larger than b+a. This reduces the problem to a sort based on a custom comparison, which is very efficient given the small array size.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3!) = O(6)	O(1)	Check all permutations of the 3 elements
Optimal	O(n log n) = O(3 log 3) = O(1)	O(n) = O(3)	Sort using custom comparison of concatenated binary strings

Algorithm Walkthrough

1. Convert each integer in the array to its binary representation without leading zeros.
2. Define a comparison rule for two binary strings a and b: a should come before b if the concatenation a+b is greater than b+a when interpreted lexicographically.
3. Sort the list of binary strings using this comparison.
4. Concatenate the sorted binary strings into a single binary string.
5. Convert the final binary string to an integer using base 2.
6. Return this integer as the result.

Why it works: Sorting the binary strings by the a+b > b+a rule guarantees that the largest possible binary string is formed. This is similar to the "largest number from array" problem, but using binary representations instead of decimal strings.

Python Solution

from typing import List

class Solution:
    def maxGoodNumber(self, nums: List[int]) -> int:
        # Step 1: Convert integers to binary strings
        binaries = [bin(num)[2:] for num in nums]
        
        # Step 2: Sort with custom comparator
        binaries.sort(key=lambda x: x*7, reverse=True)
        
        # Step 3: Concatenate sorted binaries
        result_binary = ''.join(binaries)
        
        # Step 4: Convert binary string to integer
        return int(result_binary, 2)

The code converts each number to a binary string using bin(num)[2:] to remove the '0b' prefix. It sorts the strings with a lambda key that multiplies the string to ensure proper lexicographical comparison. The sorted strings are concatenated, and int(result_binary, 2) converts the binary string to the final integer.

Go Solution

import (
    "sort"
    "strconv"
)

func maxGoodNumber(nums []int) int {
    binaries := make([]string, len(nums))
    for i, num := range nums {
        binaries[i] = strconv.FormatInt(int64(num), 2)
    }

    sort.Slice(binaries, func(i, j int) bool {
        return binaries[i]+binaries[j] > binaries[j]+binaries[i]
    })

    resultBinary := ""
    for _, b := range binaries {
        resultBinary += b
    }

    result, _ := strconv.ParseInt(resultBinary, 2, 64)
    return int(result)
}

In Go, strconv.FormatInt converts integers to binary strings. The slice is sorted using a custom comparison function. The final binary string is concatenated and converted to an integer using strconv.ParseInt. Go requires explicit 64-bit integer parsing, but this is safe given the maximum possible length of the binary string.

Worked Examples

Example 1: nums = [1, 2, 3]

1. Convert to binaries: [1, 10, 11]
2. Compare concatenations: 11+1+10 = "11110" > any other order
3. Resulting binary string: "11110"
4. Convert to integer: 30

Example 2: nums = [2, 8, 16]

1. Convert to binaries: [10, 1000, 10000]
2. Compare concatenations: "10000100010" (from [16, 8, 2])
3. Convert to integer: 1296

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting three elements, effectively constant
Space	O(n)	Store binary strings for concatenation

The complexity is dominated by the sorting operation, which is trivial for n = 3. The space complexity is proportional to storing the binary strings, also very small.

Test Cases

# Provided examples
assert Solution().maxGoodNumber([1,2,3]) == 30  # "11110"
assert Solution().maxGoodNumber([2,8,16]) == 1296  # "10100010000"

# Edge cases
assert Solution().maxGoodNumber([1,1,1]) == 7  # "111"
assert Solution().maxGoodNumber([127,1,2]) == 32639  # "1111111" + "10" + "1"
assert Solution().maxGoodNumber([5,10,15]) == 13375  # "1111" + "1010" + "101"

Test	Why
[1,2,3]	Basic small integers, checks ordering of different binary lengths
[2,8,16]	Powers of two, checks handling of different lengths
[1,1,1]	All numbers equal, ensures code handles identical binaries
[127,1,2]	Maximum allowed number, tests large binary string
[5,10,15]	Mixed small numbers, tests correct binary concatenation ordering

Edge Cases

One important edge case is when all numbers are identical, such as [1,1,1]. A naive implementation that assumes unique numbers might fail, but this algorithm correctly concatenates identical binaries in any order, giving the correct result.

Another edge case is when one number is significantly larger than the others, like [127,1,2]. Its binary representation is much longer, so it must appear first in the concatenation to maximize the result. The sorting ensures this automatically.

A final edge case involves numbers whose binary strings have similar prefixes, such as [5,10,15]. Without careful comparison, a lexicographical sort could choose the wrong order. By explicitly comparing a+b vs b+a, the algorithm ensures the optimal ordering even in tricky prefix scenarios.