Maximum Possible Number by Binary Concatenation - Solution & Explanation

Problem Overview: You are given an array of integers. Convert each number to its binary representation and concatenate them in some order. The resulting binary string represents a number. The task is to arrange the numbers so this binary concatenation produces the maximum possible value.

The challenge is not the binary conversion itself. The tricky part is choosing the order of elements. Different permutations produce different concatenated binary strings, and the one with the largest binary value (or lexicographically largest binary string) is the answer.

Approach 1: Lexicographic Concatenation (Enumeration) (Time: O(n! * k), Space: O(k))

This approach tries every possible ordering of the array. For each permutation, convert every integer to binary using bin(x) (or equivalent), concatenate the binary strings, and interpret the result as a binary number. Track the maximum value seen across all permutations.

The key idea is brute-force enumeration: since the concatenation result depends entirely on order, checking every permutation guarantees the optimal answer. If each binary string has length k, building and evaluating each candidate takes O(k). The overall complexity becomes O(n! * k).

This method is straightforward and useful for understanding the problem structure. It works well when the array size is very small (as in the original constraint). It also highlights that the problem reduces to ordering elements based on how their binary strings interact when concatenated.

Approach 2: Direct Comparison with Custom Sorting (Time: O(n log n * k), Space: O(n))

A more scalable approach treats the problem like the classic “largest number by concatenation” problem. Convert each integer to its binary string first. When deciding the order of two elements a and b, compare the concatenated strings a + b and b + a. If a + b is larger, place a before b; otherwise place b first.

This comparison rule ensures that every pair of elements contributes to the globally optimal concatenation. Sorting the array with this custom comparator yields the best order without checking every permutation. After sorting, concatenate all binary strings and convert the final binary value if needed.

The sorting step dominates the complexity at O(n log n). Each comparison may examine up to O(k) characters, where k is the binary length. This approach generalizes well and is the preferred strategy when the array size grows.

Relevant concepts include array manipulation, binary string handling from bit manipulation, and permutation reasoning from enumeration.

Recommended for interviews: Start by explaining the permutation idea to show you understand why ordering matters. Then move to the custom sorting strategy. Interviewers usually expect the comparator-based solution because it reduces factorial exploration to O(n log n) while preserving the correct ordering rule.