Maximum Possible Number by Binary Concatenation
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible orderings of the three numbers. Since the input array size is fixed at 3, there are always 3! = 6 permutations. For each permutation, we convert the numbers to their binary string representations, concatenate them, and then convert the resulting binary string back to an integer. We keep track of the maximum integer found across all permutations.
Algorithm
- Initialize a variable
maxNumto 0. - Define all 6 permutations of the indices
[0, 1, 2]. - Iterate through each permutation
p = [i, j, k]. - Get the numbers
a = nums[i],b = nums[j],c = nums[k]. - Convert
a,b,cto binary strings:s_a,s_b,s_c. - Concatenate the strings:
s_concat = s_a + s_b + s_c. - Convert
s_concatto a long integer:currentNum = Long.parseLong(s_concat, 2). - Update
maxNum = Math.max(maxNum, currentNum). - After the loop, return
maxNum.
Walkthrough
The core idea is to test every possible arrangement of the numbers in nums. The number of permutations for an array of size 3 is 3! = 6. We can either generate these permutations programmatically or hardcode them since the number is small. The permutations are: [nums[0], nums[1], nums[2]], [nums[0], nums[2], nums[1]], [nums[1], nums[0], nums[2]], [nums[1], nums[2], nums[0]], [nums[2], nums[0], nums[1]], and [nums[2], nums[1], nums[0]]. For each permutation, say [a, b, c]:
- Convert
a,b, andcto binary strings usingInteger.toBinaryString(). - Create a new string by concatenating these binary strings in order:
binary(a) + binary(b) + binary(c). - Parse this concatenated binary string into a number. Since the result can be large, it's safer to use
Long.parseLong(binaryString, 2). - Compare this number with the current maximum value and update the maximum if the new number is larger. After checking all 6 permutations, the final maximum value is the answer.
class Solution { public long maximumPossibleNumber(int[] nums) { long maxNum = 0; int[][] permutations = { {nums[0], nums[1], nums[2]}, {nums[0], nums[2], nums[1]}, {nums[1], nums[0], nums[2]}, {nums[1], nums[2], nums[0]}, {nums[2], nums[0], nums[1]}, {nums[2], nums[1], nums[0]} }; for (int[] p : permutations) { StringBuilder binaryString = new StringBuilder(); for (int num : p) { binaryString.append(Integer.toBinaryString(num)); } long currentNum = Long.parseLong(binaryString.toString(), 2); if (currentNum > maxNum) { maxNum = currentNum; } } return maxNum; }}Complexity
Time
`O(1)`. The number of permutations is constant (6). The numbers are at most 127, so their binary representations have at most 7 bits. String conversions, concatenations, and parsing take time proportional to the length of the strings, which is a small constant. Therefore, the overall time complexity is constant.
Space
`O(1)`. We use a `StringBuilder` to build the concatenated string, whose maximum length is bounded by a small constant (e.g., `3 * 7 = 21`). The space required for permutations is also constant. Thus, the space complexity is constant.
Trade-offs
Pros
Simple and easy to understand.
Directly implements the logic described in the problem.
Cons
Relies on string conversions and manipulations, which can be less performant than direct numerical operations.
Creates intermediate string objects, which might lead to minor overhead.
This approach is an optimization over the string-based method. It also checks all 6 permutations of the input numbers but performs the concatenation using efficient bitwise operations instead of string manipulation. Concatenating the binary representation of number B after A is equivalent to left-shifting A by the number of bits in B, and then performing a bitwise OR with B.
Algorithm
- Initialize a variable
maxNumto 0. - Define all 6 permutations of the indices
[0, 1, 2]. - Iterate through each permutation
p = [i, j, k]. - Get the numbers
a = nums[i],b = nums[j],c = nums[k]. - Calculate the number of bits in
bandcusing32 - Integer.numberOfLeadingZeros(num). - Calculate the concatenated value using bitwise operations:
currentNum = ((((long)a << len_b) | b) << len_c) | c. - Update
maxNum = Math.max(maxNum, currentNum). - After the loop, return
maxNum.
Walkthrough
Similar to the first approach, we iterate through all 6 permutations of the nums array. For each permutation [a, b, c], we calculate the final number numerically. The key operation is concatenating two numbers, say x and y. If y has len_y bits in its binary representation, concatenating y after x is achieved by the formula: (x << len_y) | y. To find the number of bits len_y for a positive integer y, we can use the efficient built-in function Integer.numberOfLeadingZeros(y). The number of bits is 32 - Integer.numberOfLeadingZeros(y). The process for a permutation [a, b, c] is:
- Calculate the number of bits for
b(len_b) andc(len_c). - First, concatenate
aandb:temp = ((long)a << len_b) | b. We castatolongbefore shifting to prevent overflow, as the intermediate result might exceedInteger.MAX_VALUE. - Then, concatenate
cto the result:currentNum = (temp << len_c) | c. - Compare
currentNumwith the current maximum and update if necessary. This avoids the overhead of creating and parsing strings, making it more performant.
class Solution { public long maximumPossibleNumber(int[] nums) { long maxNum = 0; int[][] permutations = { {nums[0], nums[1], nums[2]}, {nums[0], nums[2], nums[1]}, {nums[1], nums[0], nums[2]}, {nums[1], nums[2], nums[0]}, {nums[2], nums[0], nums[1]}, {nums[2], nums[1], nums[0]} }; for (int[] p : permutations) { int a = p[0]; int b = p[1]; int c = p[2]; int len_b = 32 - Integer.numberOfLeadingZeros(b); int len_c = 32 - Integer.numberOfLeadingZeros(c); long temp = ((long)a << len_b) | b; long currentNum = (temp << len_c) | c; maxNum = Math.max(maxNum, currentNum); } return maxNum; }}Complexity
Time
`O(1)`. The logic is similar to the first approach, but the operations inside the loop (bitwise shifts, ORs, and `numberOfLeadingZeros`) are extremely fast, often single CPU instructions. This makes it faster in practice than the string-based approach, although both are asymptotically O(1).
Space
`O(1)`. Only a few variables are needed to store the numbers, bit lengths, and the maximum value. No dynamic memory allocation is required.
Trade-offs
Pros
Highly efficient due to the use of bitwise operations.
Avoids the overhead of string creation and parsing.
Cons
The logic might be slightly less intuitive for those not comfortable with bit manipulation.
Requires careful handling of types (casting to
long) to prevent overflow during bit shifts.
This approach is the most elegant and scalable. It's based on the same principle as the 'Largest Number' problem. To determine the optimal order of any two numbers, a and b, we don't need to know about any other numbers. We simply compare which concatenated value is larger: the one formed by a then b, or the one formed by b then a. By sorting the entire array using this custom comparison logic, we can arrange the numbers in the optimal order to form the maximum possible concatenated number.
Algorithm
- Create a list or array of
Integerfrom the inputint[] nums. - Define a custom comparator:
- For two integers
aandb, calculate their bit lengths:len_aandlen_b. - Calculate the two possible concatenated numbers:
val1 = ((long)a << len_b) | bandval2 = ((long)b << len_a) | a. - The comparator should return a value indicating if
val2is greater than, less than, or equal toval1to achieve a descending sort.
- For two integers
- Sort the list/array using
Arrays.sort()with this custom comparator. - Iterate through the sorted list and build the final number by concatenating them one by one using bit shifts and ORs.
Walkthrough
The problem of finding the maximum number by concatenating elements can be solved by finding the correct permutation. This permutation can be found by sorting the numbers with a special comparison rule. Let's define a comparison between two numbers, a and b. We say a should come before b if the number formed by concatenating bin(a) and bin(b) is greater than the number formed by concatenating bin(b) and bin(a). Mathematically, a comes before b if ((long)a << len(b)) | b > ((long)b << len(a)) | a, where len(x) is the number of bits in x. We can implement a custom Comparator with this logic. The algorithm is:
- Convert the
int[]array to anInteger[]array to useArrays.sortwith a custom comparator. - Sort the
Integer[]array using the custom comparison logic. The comparator should order elements such thatbcomes beforeaif((long)b << len(a)) | ais greater than((long)a << len(b)) | b. This will result in a descending order according to our 'concatenation greatness' metric. - After sorting, the numbers are in the optimal order. Concatenate them in this order using the bit manipulation technique.
import java.util.Arrays;import java.util.Comparator; class Solution { public long maximumPossibleNumber(int[] nums) { Integer[] numsObj = new Integer[nums.length]; for (int i = 0; i < nums.length; i++) { numsObj[i] = nums[i]; } Arrays.sort(numsObj, (a, b) -> { int len_a = 32 - Integer.numberOfLeadingZeros(a); int len_b = 32 - Integer.numberOfLeadingZeros(b); long val1 = ((long)a << len_b) | b; long val2 = ((long)b << len_a) | a; return Long.compare(val2, val1); }); long result = 0; for (int num : numsObj) { int len = 32 - Integer.numberOfLeadingZeros(num); result = (result << len) | num; } return result; }}Complexity
Time
`O(N log N)` where `N` is the number of elements. For this problem, `N=3`, so the complexity is `O(3 log 3)`, which is constant, `O(1)`. The comparison function itself takes constant time. This approach is more general and would work efficiently for larger arrays as well.
Space
`O(N)` or `O(log N)` depending on the sort implementation's space requirements. For this problem, `N=3`, so it's `O(1)`. We also create an `Integer[]` array of size `N`.
Trade-offs
Pros
Provides a general and scalable solution that works for any number of elements, not just 3.
Elegant and based on a proven algorithmic pattern.
Avoids hardcoding permutations.
Cons
For a fixed small size of
N=3, the overhead of sorting might make it slightly less performant than the hardcoded permutation approach, although the asymptotic complexity is still constant.Requires understanding of custom comparators and sorting.
Solutions
Solution
class Solution {private int[] nums;public int maxGoodNumber(int[] nums) { this.nums = nums; int 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; }private int f(int i, int j, int k) { String a = Integer.toBinaryString(nums[i]); String b = Integer.toBinaryString(nums[j]); String c = Integer.toBinaryString(nums[k]); return Integer.parseInt(a + b + c, 2); }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.