Maximum Possible Number by Binary Concatenation

Problem Description

Given an array of three integers (each from 1 to 127), convert each integer to its binary representation (without any leading zeros), then concatenate these binary strings in any possible order. The goal is to find the permutation that yields the maximum possible decimal integer when the resulting binary string is interpreted as a binary number.

Key Insights

• The array length is fixed at 3, meaning there are only 6 possible permutations.
• For each permutation, convert the numbers to binary (no leading zeros) and then concatenate the results.
• Convert the concatenated binary string into a decimal integer.
• Since the input size is very small, a brute-force approach by checking all permutations is efficient.

Space and Time Complexity

Time Complexity: O(1) (since the number of permutations is fixed at 3! = 6)
Space Complexity: O(1) (only a few auxiliary variables are used)

Solution

The solution involves generating all permutations of the input array. For each permutation, convert each integer to its binary representation (using the built-in conversion methods), concatenate these binary strings, and then convert the result to a decimal integer. Finally, track and return the maximum value found.

Data structures used:

• Arrays (or lists) to hold numbers.
• Strings to build up binary representations.
• Algorithms: Permutation generation and string manipulation.

Key steps include:

1. Generate all possible orders of the 3 numbers.
2. For each permutation, obtain the binary string for each integer and concatenate them.
3. Convert the concatenated binary string into its corresponding decimal value.
4. Compare and update the maximum value.

Code Solutions