Is Maximum Possible Number by Binary Concatenation easy or hard?

The problem is rated Medium because the main challenge is recognizing the ordering rule for concatenation. Once you reduce it to a custom sorting problem similar to the 'largest number' pattern, the implementation becomes straightforward.

Maximum Possible Number by Binary Concatenation Python/Java solution

In Python or Java, convert each number to a binary string and sort using a custom comparator that checks which concatenation (a+b or b+a) produces the larger binary value. After sorting, join the binary strings and convert the result if a numeric value is required.

What is the best approach for Maximum Possible Number by Binary Concatenation?

The most practical approach is sorting numbers using a custom comparator. Convert each integer to its binary string and compare pairs using (a+b) vs (b+a). Sorting with this rule produces the optimal order in O(n log n * k) time, where k is the binary string length.

Is Maximum Possible Number by Binary Concatenation asked at Google/Amazon/Meta?

Problems based on concatenation ordering and custom comparators appear frequently in big tech interviews. Variants of the 'largest concatenated number' problem are common at companies like Amazon, Google, and Meta, especially when testing sorting logic and string comparisons.

What data structure is used in Maximum Possible Number by Binary Concatenation?

The primary structure is an array of integers that is transformed into an array of binary strings. Sorting with a custom comparator is the core operation, along with string concatenation for comparisons.

What is the time complexity of Maximum Possible Number by Binary Concatenation?

The brute-force permutation approach runs in O(n! * k) time because it checks every possible ordering. The optimized solution uses custom sorting and runs in O(n log n * k), where k is the maximum binary length used during concatenation comparisons.

Description Hints 1 Solution Video 7:03

3309. Maximum Possible Number by Binary Concatenation

Q: How to solve Maximum Possible Number by Binary Concatenation in O(n log n)?

Convert each number to its binary representation and store them as strings. Sort the strings using a comparator that compares a+b with b+a. This ensures the pairwise order produces the largest concatenated binary string, giving an overall O(n log n * k) complexity.

Medium64.9% acceptance2 companies

You are given an array of integers nums of size 3.

Return the maximum possible number whose binary representation can be formed by concatenating the binary representation of all elements in nums in some order.

Note that the binary representation of any number does not contain leading zeros.

Example 1:

Input: nums = [1,2,3]

Output: 30

Explanation:

Concatenate the numbers in the order [3, 1, 2] to get the result "11110", which is the binary representation of 30.

Example 2:

Input: nums = [2,8,16]

Output: 1296

Explanation:

Concatenate the numbers in the order [2, 8, 16] to get the result "10100010000", which is the binary representation of 1296.

Constraints:

nums.length == 3
1 <= nums[i] <= 127

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

How many possible concatenation orders are there?

7:03

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution