3309. Maximum Possible Number by Binary Concatenation

Posted on Edited on In

3309. Maximum Possible Number by Binary Concatenation

Description

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:

1
2
3
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:

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

Hints/Notes

Solution

Language: C++

nlogn solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxGoodNumber(vector<int>& nums) {
        ranges::sort(nums, [](int a, int b) {
            int len_a = __lg(a) + 1;
            int len_b = __lg(b) + 1;
            return (a << len_b | b) > (b << len_a | a);
        });

        int ans = 0;
        for (int x : nums) {
            ans = ans << (__lg(x) + 1) | x;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxGoodNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (j == i) {
                    continue;
                }
                int k = 3 - i - j;
                int bit1 = __lg(nums[j]) + 1,
                    bit2 = __lg(nums[k]) + 1;
                int tmp =
                    (nums[i] << (bit1 + bit2)) + (nums[j] << bit2) + nums[k];
                res = max(tmp, res);
            }
        }
        return res;
    }
};