3309. Maximum Possible Number by Binary Concatenation

MediumBit ManipulationArrayEnumeration

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Given the problem constraints, the array nums always has a size of 3. Our goal is to determine the maximum number that can be achieved by concatenating the binary representations of these integers in any possible order.

The approach utilizes the fact that for an array of three elements, there are only 3! = 6 possible permutations. We can thoroughly explore all these permutations to find out which one yields the highest number when its elements' binary representations are concatenated. For each permutation, convert each integer to its binary form, concatenate these binaries as a string, then transform the result back into a decimal number to compare against the current maximum. This exhaustive enumeration ensures that the best possible combination is selected for the maximum binary concatenation.

Solution Approach

The solution involves a straightforward implementation using permutation and string manipulation techniques. Here's how it's accomplished:

Generate Permutations: Since nums has only three elements, enumerate all possible permutations of the array. This results in a total of 3! = 6 permutations.
Binary Conversion and Concatenation:
- For each permutation, convert each number to its binary representation using Python's bin() function. Use slicing bin(i)[2:] to remove the '0b' prefix that Python includes in its binary strings.
- Concatenate these binary strings for the entire permutation to form one single binary sequence.
Conversion to Decimal and Comparison:
- Convert the obtained binary string back into a decimal number using int(string, 2).
- Keep track of the maximum value encountered across all permutations in a variable ans.
Output the Maximum: Once all permutations are traversed, ans will hold the maximum decimal value from all possible binary concatenations.

This approach systematically explores each order of the given numbers' binary representations, ensuring that no potential combination is overlooked. Given the fixed small size of the input array, the computational cost remains manageable.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using the example array nums = [1, 2, 3].

Generate Permutations: First, we generate all 6 permutations of the array nums since it contains 3 elements. The permutations are:
1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]
Binary Conversion and Concatenation:
- For each permutation, convert each number to its binary representation:
  - 1 in binary is 1
  - 2 in binary is 10
  - 3 in binary is 11
- Concatenate the binaries:
  - For permutation [1, 2, 3], the concatenation is 11011 (i.e., 1 + 10 + 11)
  - Repeat this for all permutations:
    - [1, 3, 2] -> 1110
    - [2, 1, 3] -> 1011
    - [2, 3, 1] -> 10111
    - [3, 1, 2] -> 1110
    - [3, 2, 1] -> 11101
Conversion to Decimal and Comparison:
- Convert each concatenated binary string into a decimal number:
  - 11011 is 27
  - 1110 is 14
  - 1011 is 11
  - 10111 is 23
  - 1110 is 14
  - 11101 is 29
- Compare these values to find the maximum. The highest decimal value is 29.
Output the Maximum: The maximum decimal value obtained is 29, from the binary 11101 corresponding to the permutation [3, 2, 1].

This demonstrates how to systematically explore permutations to find the optimal binary concatenation resulting in the maximum numerical value.

Solution Implementation

1from itertools import permutations
2from typing import List
3
4class Solution:
5    def maxGoodNumber(self, nums: List[int]) -> int:
6        # Initialize the answer to zero
7        ans = 0
8      
9        # Generate all possible permutations of the list nums
10        for arr in permutations(nums):
11            # Create a binary string by converting each number in the permutation to binary
12            # Skip the '0b' prefix for each binary representation
13            # Join them together to form one large binary string
14            binary_string = "".join(bin(i)[2:] for i in arr)
15          
16            # Convert the binary string to an integer
17            num = int(binary_string, 2)
18          
19            # Update the answer with the maximum number found
20            ans = max(ans, num)
21      
22        # Return the largest number that can be formed
23        return ans
24

1class Solution {
2    private int[] nums;
3
4    /**
5     * Finds the maximum good number by combining the binary strings
6     * of three different numbers from the given array.
7     *
8     * @param nums an array of integers
9     * @return the maximum good number
10     */
11    public int maxGoodNumber(int[] nums) {
12        this.nums = nums;
13      
14        // Calculate the good number by trying all permutations of indices
15        int ans = f(0, 1, 2);
16        ans = Math.max(ans, f(0, 2, 1));
17        ans = Math.max(ans, f(1, 0, 2));
18        ans = Math.max(ans, f(1, 2, 0));
19        ans = Math.max(ans, f(2, 0, 1));
20        ans = Math.max(ans, f(2, 1, 0));
21      
22        return ans;
23    }
24
25    /**
26     * Computes a good number by concatenating the binary representations
27     * of the numbers at the specified indices and parsing the result as a binary number.
28     *
29     * @param i the index of the first number
30     * @param j the index of the second number
31     * @param k the index of the third number
32     * @return the good number formed by concatenating the binary strings
33     */
34    private int f(int i, int j, int k) {
35        // Convert the numbers to their binary string representation
36        String binaryA = Integer.toBinaryString(nums[i]);
37        String binaryB = Integer.toBinaryString(nums[j]);
38        String binaryC = Integer.toBinaryString(nums[k]);
39      
40        // Concatenate the binary strings and parse it back to an integer
41        return Integer.parseInt(binaryA + binaryB + binaryC, 2);
42    }
43}
44

1class Solution {
2public:
3    int maxGoodNumber(std::vector<int>& nums) {
4        int ans = 0;
5
6        // Lambda function to evaluate a 'good number' from the current permutation
7        auto calculateGoodNumber = [&](std::vector<int>& nums) {
8            int res = 0;
9            std::vector<int> bitRepresentation;
10
11            // Convert each number to its binary form and store the bits in "bitRepresentation"
12            for (int x : nums) {
13                while (x) {
14                    bitRepresentation.push_back(x & 1); // Store the least significant bit
15                    x >>= 1; // Shift right to process the next bit
16                }
17            }
18
19            // Convert the bit representation back to a decimal number
20            while (!bitRepresentation.empty()) {
21                res = res * 2 + bitRepresentation.back(); // Generate the number from bits
22                bitRepresentation.pop_back(); // Remove the last bit
23            }
24
25            return res;
26        };
27
28        // Iterate and attempt to maximize the 'good number' over 6 permutations
29        for (int i = 0; i < 6; ++i) {
30            ans = std::max(ans, calculateGoodNumber(nums));
31            std::next_permutation(nums.begin(), nums.end()); // Generate the next permutation
32        }
33
34        return ans;
35    }
36};
37

1// Function to calculate the maximum possible number by concatenating
2// the binary representations of three different numbers from the array.
3function maxGoodNumber(nums: number[]): number {
4
5    // Helper function that concatenates the binary representations
6    // of nums[i], nums[j], and nums[k], and converts the result back to a decimal number.
7    const f = (i: number, j: number, k: number): number => {
8        const a = nums[i].toString(2); // Convert nums[i] to a binary string.
9        const b = nums[j].toString(2); // Convert nums[j] to a binary string.
10        const c = nums[k].toString(2); // Convert nums[k] to a binary string.
11        const res = parseInt(a + b + c, 2); // Concatenate the strings and convert back to a decimal number.
12        return res;
13    };
14
15    // Initialize 'ans' with the result of the first combination.
16    let ans = f(0, 1, 2);
17
18    // Compare and update 'ans' with all possible permutations of the first three numbers.
19    ans = Math.max(ans, f(0, 2, 1));
20    ans = Math.max(ans, f(1, 0, 2));
21    ans = Math.max(ans, f(1, 2, 0));
22    ans = Math.max(ans, f(2, 0, 1));
23    ans = Math.max(ans, f(2, 1, 0));
24
25    // Return the maximum value found.
26    return ans;
27}
28

Time and Space Complexity

The given code's time complexity is influenced by the permutations function and the construction of binary numbers. The primary time-consuming operation is generating permutations of nums. If n is the length of nums, generating permutations has a complexity of O(n!).

For each permutation, the code constructs a binary string representation and converts it to an integer. Suppose the sum of the lengths of all binary strings for all numbers in nums is L, creating a binary string for one permutation is O(L), generating the integer from this string is O(\log M) where M is the maximum possible value of the binary number.

Thus, the overall time complexity is O(n! * L) where L is assumed to be small compared to n!.

The space complexity is constant O(1) as there's no usage of extra space that scales with any input parameter size; permutations use constant space beyond inputs, and only a few auxiliary variables are used.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know