#3309

Medium

LeetCode Problem Workspace

Maximum Possible Number by Binary Concatenation

Determine the largest number achievable by reordering three integers and concatenating their binary forms efficiently.

Problem Statement

You are given an array nums of three integers. Your task is to reorder these integers and concatenate their binary representations in any sequence to create the largest possible number. Each number's binary form should not have leading zeros.

Return the decimal value of the maximum number obtained by all possible concatenation orders. Consider the problem's core pattern of combining array manipulation with bit-level binary operations to find the optimal sequence.

Examples

Example 1

Input: nums = [1,2,3]

Output: 30

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

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

Solution Approach

Generate All Permutations

Since nums has exactly three elements, generate all 3! = 6 possible orders. Each permutation represents a potential binary concatenation sequence, ensuring no order is skipped.

Concatenate Binary Representations

For each permutation, convert every integer to its binary string without leading zeros, then join them in sequence. Convert the resulting binary string back to an integer to compute its numeric value.

Compare and Return Maximum

Track the maximum integer obtained from all permutations. Return this value as the solution. This step directly addresses the pattern of maximizing output through bit-level ordering.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is constant O(6) due to fixed 3-element array, as all permutations are evaluated. Space complexity is also O(1) aside from temporary binary strings, since only the maximum value is stored.

What Interviewers Usually Probe

Consider all 3! permutations to avoid missing the maximum binary concatenation.
Binary conversion should exclude leading zeros to match correct decimal output.
Optimal solution leverages small array size and direct permutation checks rather than sorting heuristics.

Common Pitfalls or Variants

Common pitfalls

Adding leading zeros to binary strings can yield incorrect numeric results.
Forgetting to check all six permutations may miss the true maximum.
Attempting complex bit manipulation tricks for a fixed small array wastes time.

Follow-up variants

Extend to arrays longer than 3, requiring more efficient ordering or greedy heuristics.
Allow repeated numbers and check whether duplicate permutations affect the result.
Maximize binary concatenation but return the binary string instead of decimal.

FAQ

What is the best way to maximize the number by binary concatenation?

Generate all permutations of the array and convert each to binary, then find the decimal value of the largest concatenated result.

Do leading zeros in binary representation affect the result?

Yes, leading zeros are ignored in binary conversion. Include only minimal binary digits for each number to get the correct decimal value.

Why is this considered an Array plus Bit Manipulation pattern?

It combines array permutation logic with direct manipulation of binary representations, requiring both ordering and bit-level evaluation.

Can this approach handle arrays longer than three elements?

For longer arrays, generating all permutations becomes impractical, and a greedy or sorting-based method may be required.

How does GhostInterview help with 'Maximum Possible Number by Binary Concatenation'?

It automates binary conversion and permutation testing, highlighting the exact sequence yielding the maximum decimal value efficiently.

terminal

Solution

Solution 1: Enumeration

According to the problem description, the length of the array $\textit{nums}$ is $3$. We can enumerate all permutations of $\textit{nums}$, which has $3! = 6$ permutations. Then, we convert the elements of the permuted array into binary strings, concatenate these binary strings, and finally convert the concatenated binary string into a decimal number to get the maximum value.

1

2

3

4

5

6

7

class Solution:
    def maxGoodNumber(self, nums: List[int]) -> int:
        ans = 0
        for arr in permutations(nums):
            num = int("".join(bin(i)[2:] for i in arr), 2)
            ans = max(ans, num)
        return ans

Continue Practicing

#3435 frequencies of shortest supersequences #3514 number of unique xor triplets ii #3566 partition array into two equal product subsets