# Maximum Possible Number by Binary Concatenation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-possible-number-by-binary-concatenation)
Canonical: https://scaleengineer.com/dsa/problems/maximum-possible-number-by-binary-concatenation
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## Problem
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 == 3`
* `1 <= nums[i] <= 127`

# Approaches
## Brute-Force with String Manipulation
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.
**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.
**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.
### Explanation
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]`:
1. Convert `a`, `b`, and `c` to binary strings using `Integer.toBinaryString()`.
2. Create a new string by concatenating these binary strings in order: `binary(a) + binary(b) + binary(c)`.
3. Parse this concatenated binary string into a number. Since the result can be large, it's safer to use `Long.parseLong(binaryString, 2)`.
4. 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.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `maxNum` to 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`, `c` to binary strings: `s_a`, `s_b`, `s_c`.
- Concatenate the strings: `s_concat = s_a + s_b + s_c`.
- Convert `s_concat` to a long integer: `currentNum = Long.parseLong(s_concat, 2)`.
- Update `maxNum = Math.max(maxNum, currentNum)`.
- After the loop, return `maxNum`.

## Optimized Brute-Force with Bit Manipulation
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`.
**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.
**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.
### Explanation
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:
1. Calculate the number of bits for `b` (`len_b`) and `c` (`len_c`).
2. First, concatenate `a` and `b`: `temp = ((long)a << len_b) | b`. We cast `a` to `long` before shifting to prevent overflow, as the intermediate result might exceed `Integer.MAX_VALUE`.
3. Then, concatenate `c` to the result: `currentNum = (temp << len_c) | c`.
4. Compare `currentNum` with the current maximum and update if necessary.
This avoids the overhead of creating and parsing strings, making it more performant.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `maxNum` to 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 `b` and `c` using `32 - 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`.

## Optimal Solution via Custom Sorting
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.
**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`.
**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.
### Explanation
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:
1. Convert the `int[]` array to an `Integer[]` array to use `Arrays.sort` with a custom comparator.
2. Sort the `Integer[]` array using the custom comparison logic. The comparator should order elements such that `b` comes before `a` if `((long)b << len(a)) | a` is greater than `((long)a << len(b)) | b`. This will result in a descending order according to our 'concatenation greatness' metric.
3. After sorting, the numbers are in the optimal order. Concatenate them in this order using the bit manipulation technique.

```java
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;
    }
}
```
### Algorithm
- Create a list or array of `Integer` from the input `int[] nums`.
- Define a custom comparator:
  - For two integers `a` and `b`, calculate their bit lengths: `len_a` and `len_b`.
  - Calculate the two possible concatenated numbers: `val1 = ((long)a << len_b) | b` and `val2 = ((long)b << len_a) | a`.
  - The comparator should return a value indicating if `val2` is greater than, less than, or equal to `val1` to achieve a descending sort.
- 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```