Skip to content

3309. Maximum Possible Number by Binary Concatenation 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 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 ans = 0;

    ranges::sort(nums,
                 [this](int a, int b) { return concat(a, b) > concat(b, a); });

    for (const int num : nums)
      ans = concat(ans, num);

    return ans;
  }

 private:
  // Returns the concatenation of the binary representations of a and b.
  int concat(int a, int b) {
    return (a << static_cast<int>(log2(b)) + 1) + b;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int maxGoodNumber(int[] nums) {
    int ans = 0;
    Integer[] boxedNums = Arrays.stream(nums).boxed().toArray(Integer[] ::new);

    Arrays.sort(boxedNums, (a, b) -> Integer.compare(concat(b, a), concat(a, b)));

    for (final int num : boxedNums)
      ans = concat(ans, num);

    return ans;
  }

  // Returns the concatenation of the binary representations of a and b.
  private int concat(int a, int b) {
    return a * (Integer.highestOneBit(b) << 1) + b;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def maxGoodNumber(self, nums: list[int]) -> int:
    ans = 0

    def concat(a: int, b: int) -> int:
      """Returns the concatenation of the binary representations of a and b."""
      return (a << b.bit_length()) + b

    nums.sort(key=functools.cmp_to_key(
        lambda a, b: concat(b, a) - concat(a, b)))

    for num in nums:
      ans = concat(ans, num)

    return ans