Maximum Possible Number by Binary Concatenation solution and explanation
Google
8 more videos on this problem
Leetcode Weekly Contest 418 | 3309. Maximum Possible Number by Binary Concatenation |CodeFod · 7:03 · 479 views
3309. Maximum Possible Number by Binary Concatenation (Leetcode Easy)Programming Live with Larry · 5:58 · 402 views
Maximum Possible Number by Binary Concatenation | Leetcode weekly-contest-418Developer Coder · 4:14 · 265 views
Leetcode 3309 | Maximum Possible Number by Binary Concatenation | Weekly Contest 418Road To FAANG · 5:11 · 145 views
3309. Maximum Possible Number by Binary Concatenation | Leetcode | POTD | Let's PracticeLet's Practice Together · 13:49 · 133 views
3309. Maximum Possible Number by Binary Concatenation | Leetcode Weekly-418 | Editorial #contestCodeLearnCode · 3:46 · 74 views
3309. Maximum Possible Number by Binary Concatenation || Leetcode contest || Weekly Contest 418 LolCode · 5:54 · 61 views
🄵🄰🄸🄻 Leetcode 3309 Maximum Possible Number by Binary ConcatenationPass OR Fail: Coding Journey · 22:01 · 45 views
Leetcode 3309. Maximum Possible Number by Binary Concatenation (bit)LetsCode · 2:21 · 12 views
The problem
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 == 31 <= nums[i] <= 127
Approach overview
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.
Approach 1: Lexicographic Concatenation
This approach involves treating the binary representations of the numbers as strings and finding the permutation that forms the maximum possible concatenated binary string.
Since there are only 3 numbers, we can afford to try all permutations and select the best one by comparing lexicographically string concatenations in each permutation.
from itertools import permutations
def max_binary_concat(nums):
perms = permutations(nums)
max_num = 0
for perm in perms:
binary_concat = ''.join(format(num, 'b') for num in perm)
decimal_value = int(binary_concat, 2)
max_num = max(max_num, decimal_value)
return max_num
# Example usage
print(max_binary_concat([1, 2, 3])) # Output: 30
print(max_binary_concat([2, 8, 16])) # Output: 1296import java.util.*;
public class MaxBinaryConcat {
public static int maxBinaryConcat(int[] nums) {
int maxVal = 0;
List<Integer> numList = Arrays.asList(nums[0], nums[1], nums[2]);
for (List<Integer> perm : permutations(numList)) {
StringBuilder binaryConcat = new StringBuilder();
for (int num : perm) {
binaryConcat.append(Integer.toBinaryString(num));
}
int value = Integer.parseInt(binaryConcat.toString(), 2);
maxVal = Math.max(maxVal, value);
}
return maxVal;
}
private static List<List<Integer>> permutations(List<Integer> nums) {
if (nums.size() == 0) return Collections.singletonList(new ArrayList<>());
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.size(); i++) {
List<Integer> current = new ArrayList<>(nums);
Integer currentNumber = current.remove(i);
for (List<Integer> perm : permutations(current)) {
perm.add(0, currentNumber);
result.add(perm);
}
}
return result;
}
public static void main(String[] args) {
System.out.println(maxBinaryConcat(new int[]{1, 2, 3})); // Output: 30
System.out.println(maxBinaryConcat(new int[]{2, 8, 16})); // Output: 1296
}
}This Python implementation uses itertools.permutations to generate all possible permutations of the input array. For each permutation, it converts each number to its binary form using format(num, 'b'), concatenates the strings, converts the result back to a decimal integer using int with base 2, and tracks the maximum value found.
Time Complexity: O(3!), as there are 6 permutations of the 3 numbers, and for each permutation, concatenating binary strings takes constant time.
Space Complexity: O(1), as we use constant space apart from the input and output size.
Approach 2: Direct Comparison with Custom Sorting
Instead of generating all permutations, this approach involves sorting the numbers based on a custom comparison. We compare which order of two numbers creates a larger concatenated binary number, and sort based on that for a greedy solution to find the order that gives the maximal number.
function maxBinaryConcat(nums) {
nums.sort((a, b) => {
let ab = BigInt('0b' + a.toString(2) + b.toString(2));
let ba = BigInt('0b' + b.toString(2) + a.toString(2));
return ba - ab;
});
return parseInt(nums.map(num => num.toString(2)).join(''), 2);
}
console.log(maxBinaryConcat([1, 2, 3])); // Output: 30
console.log(maxBinaryConcat([2, 8, 16])); // Output: 1296#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int num1 = *(int*)a;
int num2 = *(int*)b;
char ab[24], ba[24];
sprintf(ab, "%s%s", itoa(num1, NULL, 2), itoa(num2, NULL, 2));
sprintf(ba, "%s%s", itoa(num2, NULL, 2), itoa(num1, NULL, 2));
return strcmp(ba, ab);
}
int maxBinaryConcat(int nums[3]) {
qsort(nums, 3, sizeof(int), compare);
char binary_concat[75] = "";
for (int i = 0; i < 3; i++) {
sprintf(binary_concat + strlen(binary_concat), "%s", itoa(nums[i], NULL, 2));
}
return strtol(binary_concat, NULL, 2);
}
int main() {
int nums1[] = {1, 2, 3};
int nums2[] = {2, 8, 16};
printf("%d\n", maxBinaryConcat(nums1)); // Output: 30
printf("%d\n", maxBinaryConcat(nums2)); // Output: 1296
return 0;
}The JavaScript solution uses Array.sort with a custom comparator to decide the order based on which concatenated result is larger. After sorting, we concatenate the binary strings and convert it to a decimal number for the result.
Time Complexity: O(n log n), due to sorting, but with n being constant (3 elements), it's O(1).
Space Complexity: O(1), as we just store intermediate results and re-use input space.
Approach 3: Enumeration
According to the problem description, the length of the array nums is 3. We can enumerate all permutations of 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.
The time complexity is O(log M), where M represents the maximum value of the elements in nums. The space complexity is O(1).
class Solution {
public:
int maxGoodNumber(vector<int>& nums) {
int ans = 0;
auto f = [&](vector<int>& nums) {
int res = 0;
vector<int> t;
for (int x : nums) {
for (; x; x >>= 1) {
t.push_back(x & 1);
}
}
while (t.size()) {
res = res * 2 + t.back();
t.pop_back();
}
return res;
};
for (int i = 0; i < 6; ++i) {
ans = max(ans, f(nums));
next_permutation(nums.begin(), nums.end());
}
return ans;
}
};function maxGoodNumber(nums: number[]): number {
const f = (i: number, j: number, k: number): number => {
const a = nums[i].toString(2);
const b = nums[j].toString(2);
const c = nums[k].toString(2);
const res = parseInt(a + b + c, 2);
return res;
};
let ans = f(0, 1, 2);
ans = Math.max(ans, f(0, 2, 1));
ans = Math.max(ans, f(1, 0, 2));
ans = Math.max(ans, f(1, 2, 0));
ans = Math.max(ans, f(2, 0, 1));
ans = Math.max(ans, f(2, 1, 0));
return ans;
}func maxGoodNumber(nums []int) int {
f := func(i, j, k int) int {
a := strconv.FormatInt(int64(nums[i]), 2)
b := strconv.FormatInt(int64(nums[j]), 2)
c := strconv.FormatInt(int64(nums[k]), 2)
res, _ := strconv.ParseInt(a+b+c, 2, 64)
return int(res)
}
ans := f(0, 1, 2)
ans = max(ans, f(0, 2, 1))
ans = max(ans, f(1, 0, 2))
ans = max(ans, f(1, 2, 0))
ans = max(ans, f(2, 0, 1))
ans = max(ans, f(2, 1, 0))
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Lexicographic Concatenation | Time Complexity: O(3!), as there are 6 permutations of the 3 numbers, and for each permutation, concatenating binary strings takes constant time. Space Complexity: O(1), as we use constant space apart from the input and output size. |
| Direct Comparison with Custom Sorting | Time Complexity: O(n log n), due to sorting, but with n being constant (3 elements), it's O(1). Space Complexity: O(1), as we just store intermediate results and re-use input space. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Lexicographic Concatenation (Permutation Enumeration) | O(n! * k) | O(k) | When the array size is very small and you want a simple brute‑force solution to verify correctness. |
| Custom Sorting with Binary Concatenation Comparison | O(n log n * k) | O(n) | General case. Preferred approach for interviews and larger arrays. |
Frequently asked questions
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.
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.
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.