Maximum Possible Number by Binary Concatenation

Medium
1338.

Maximum Possible Number by Binary Concatenation

Maximum Possible Number by Binary Concatenation is a medium coding problem on arrays, bit manipulation and enumeration, asked in Amazon and Google interviews.

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 == 3
  • 1 <= nums[i] <= 127
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxGoodNumber = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 == 3
  • 1 <= nums[i] <= 127

Hints for Maximum Possible Number by Binary Concatenation

  1. Hint 1

    There are only 3! = 6 orders. Try them all.

  2. Hint 2

    Concatenating x before y in binary is (x << bits(y)) | y, where bits(y) is the length of y in binary.

  3. 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

  1. For each number compute its binary length bits(v) by shifting until it reaches 0.
  2. For each of the 6 permutations (p, q, r), form ((p << bits(q)) | q) << bits(r) | r.
  3. 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 best

Java

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