Maximum Possible Number by Binary Concatenation — Solution
Maximum Possible Number by Binary Concatenation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Possible Number by Binary Concatenation is a medium coding problem on arrays, bit manipulation and enumeration, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of exactly three positive integers. Arrange the three numbers in some order and write their binary representations one after another (each without leading zeros) to form a single binary string.
Return the largest number, in decimal, that such a concatenation can represent.
Example 1
Input: nums = [5,1,4]
Output: 108
Explanation: The order 1, 5, 4 gives "1" + "101" + "100" = "1101100" = 108.
Example 2
Input: nums = [127,127,127]
Output: 2097151
Explanation: Twenty-one ones.
Example 3
Input: nums = [6,9,1]
Output: 233
Explanation: "1" + "110" + "1001" = "11101001".
Constraints
nums.length == 31 <= nums[i] <= 127
Hints for Maximum Possible Number by Binary Concatenation
Hint 1
There are only 3! = 6 orders. Try them all.
Hint 2
Concatenating
xbeforeyin binary is(x << bits(y)) | y, wherebits(y)is the length ofyin binary.Hint 3
The result has at most 21 bits, so it fits easily in a 32-bit integer.
How to solve Maximum Possible Number by Binary Concatenation
With three numbers there are six orders; compute the concatenated value of each with shifts and keep the largest.
Approach
- For each number compute its binary length
bits(v)by shifting until it reaches 0. - For each of the 6 permutations
(p, q, r), form((p << bits(q)) | q) << bits(r) | r. - Return the maximum.
Why it works
Writing y's bits after x's is the same as shifting x left by y's length and OR-ing y in, so each permutation's value is computed exactly; the maximum over all six orders is the answer by definition.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Shift by the binary length of the following number, not by a fixed 7 bits — leading zeros are not written.
- Sorting by the numbers' values is wrong: 1 then 5 beats 5 then 1 here because "1101" > "1011".
- All three numbers must be used exactly once.
Reference solution
Python
from typing import List
from itertools import permutations
def maxGoodNumber(nums: List[int]) -> int:
best = 0
for p in permutations(nums):
v = 0
for x in p:
v = (v << x.bit_length()) | x
best = max(best, v)
return bestJava
public static int maxGoodNumber(int[] nums) {
int[][] perms = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
int best = 0;
for (int[] p : perms) {
int v = 0;
for (int i : p) {
int x = nums[i];
int len = 32 - Integer.numberOfLeadingZeros(x);
v = (v << len) | x;
}
best = Math.max(best, v);
}
return best;
}C++
int maxGoodNumber(vector<int>& nums) {
vector<int> p(nums);
sort(p.begin(), p.end());
int best = 0;
do {
int v = 0;
for (int x : p) {
int len = 0;
for (int y = x; y > 0; y >>= 1) len++;
v = (v << len) | x;
}
best = max(best, v);
} while (next_permutation(p.begin(), p.end()));
return best;
}JavaScript
var maxGoodNumber = function(nums) {
var perms = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]];
var best = 0;
for (var p = 0; p < 6; p++) {
var v = 0;
for (var t = 0; t < 3; t++) {
var x = nums[perms[p][t]], len = 0;
for (var y = x; y > 0; y >>= 1) len++;
v = (v << len) | x;
}
if (v > best) best = v;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation