Jobs

Interviews

Discussions

Maximum Possible Number by Binary Concatenation

Medium

Asked by:

27 views

Topics:

ArraysBit Manipulation

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

Try coding it in LeetCode

Maximum Possible Number by Binary Concatenation

Medium

Asked by:

27 views

Topics:

ArraysBit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Are negative numbers allowed?
If no two numbers can be concatenated to form a larger number than any other concatenation, what should be returned? (e.g., an empty string, null, or a specific error code)?
Are there any constraints on the size of the integer array?
If concatenating A+B and B+A result in the same number, which ordering should be preferred?
Is the input guaranteed to contain valid integers, or could there be null values or other unexpected data types?

Brute Force Solution

Approach

The brute force approach is like trying every single possible combination to find the best one. In this problem, we will generate every possible pairing and ordering of the numbers, and then check each combination to see which results in the largest number when they are put together.

Here's how the algorithm would work step-by-step:

Take all the numbers you have.
Generate every single possible order in which you can arrange these numbers. For example, if you have two numbers, you try Number 1 followed by Number 2, and then Number 2 followed by Number 1.
For each of these orders, take the first two numbers and join them together to form a single larger number.
Compare this larger number to the number you would get if you joined the numbers in the opposite order.
Keep track of which way of joining the numbers results in the bigger combined number.
Do this for all possible pairs of numbers in all the different orders you created in the second step.
After doing this for every possible combination of numbers in every possible order, find the biggest combined number you encountered. This is the solution.

Code Implementation

def find_maximum_number_by_binary_concatenation(numbers):
    from itertools import permutations

    maximum_combined_number = ""

    # Generate all possible permutations of the input numbers.
    for permutation in permutations(numbers):
        
        for first_index in range(len(permutation)):
            for second_index in range(first_index + 1, len(permutation)):

                #Create a pair for concatenation
                first_number = str(permutation[first_index])
                second_number = str(permutation[second_index])

                combined_number_one = first_number + second_number
                combined_number_two = second_number + first_number

                # Compare which concatenation is larger.
                if combined_number_one > combined_number_two:
                    larger_combined_number = combined_number_one
                else:
                    larger_combined_number = combined_number_two

                #Update largest number found so far.
                if larger_combined_number > maximum_combined_number:
                    maximum_combined_number = larger_combined_number
    
    return maximum_combined_number

Big(O) Analysis

Time Complexity

O(n! * n^2) – The algorithm generates all permutations of the input array of size n, which takes O(n!) time. For each permutation, it iterates through all possible pairs of numbers. There are approximately n choose 2 which is n * (n-1)/2 pairs which is O(n^2) pairs. For each pair, it compares two concatenated numbers which takes constant time. Thus, generating all permutations and checking concatenation results in O(n! * n^2) time complexity.

Space Complexity

O(N!) – The dominant space complexity comes from generating all possible orderings (permutations) of the input numbers. To store these permutations, we may need to store a list of all permutations, or keep track of the current permutation during the process of comparing concatenations. The number of permutations for N numbers is N! which determines the space required to store all possible orderings. Thus, the auxiliary space required grows factorially with the input size N.

Optimal Solution

Approach

The goal is to arrange numbers to create the largest possible number after combining them. We achieve this by comparing how numbers look when placed next to each other and prioritizing the arrangement that yields the larger combined value.

Here's how the algorithm would work step-by-step:

First, understand that simply sorting the numbers from largest to smallest doesn't work. For example, 9 and 95: 959 is smaller than 995.
The key is to compare two numbers by placing them next to each other in both possible orders. For instance, compare combining Number A then Number B versus combining Number B then Number A.
Decide which order makes a larger number. Use this comparison to sort all the numbers.
Once the numbers are in the correct order, just string them together to form the final largest possible number.

Code Implementation

def find_maximum_number_by_concatentation(number_list):

    # Custom comparison for sorting
    def compare_numbers(number1, number2):
        string1 = str(number1) + str(number2)
        string2 = str(number2) + str(number1)
        
        if string1 > string2:
            return -1
        elif string1 < string2:
            return 1
        else:
            return 0

    # Sort the numbers using custom comparison
    sorted_numbers = sorted(number_list, key=cmp_to_key(compare_numbers))

    # Combine numbers to get maximum number
    maximum_number = ''.join(map(str, sorted_numbers))
    return maximum_number

from functools import cmp_to_key

# We need a custom comparison function for sorting.
# Standard sorting won't work in this case.

# After sorting, concatenate into a single string.

Big(O) Analysis

Time Complexity

O(n log n) – The dominant factor in the time complexity comes from sorting the input array of n numbers using a custom comparison function. The comparison function itself takes constant time since it only involves comparing the concatenations of two numbers. Common sorting algorithms like mergesort or quicksort have a time complexity of O(n log n). The concatenation and comparisons within the sorting algorithm do not increase the complexity beyond that of the sort itself.

Space Complexity

O(N) – The primary auxiliary space usage comes from sorting the input numbers based on the custom comparison. While many sorting algorithms exist, a typical implementation like `sorted()` in Python, which might use Timsort, creates a new list of size N to store the sorted elements, where N is the number of input numbers. The comparison function itself uses constant space. Thus, the dominant factor is the space for the sorted list.

Edge Cases

Case	How to Handle
Empty input array	Return an empty string or throw an exception, depending on requirements, as no concatenation is possible.
Input array with a single element	Return the single element as a string since no concatenation partner exists.
Array with large numbers causing potential integer overflow after concatenation	Use string concatenation and compare the resulting strings lexicographically to avoid integer overflow issues.
Input array containing only zeros	The result should be a string of zeros concatenated, sorted based on which zero gives the bigger result when placed first.
Input array contains numbers with different lengths and leading zeros	String comparison must handle the leading zeros and variable lengths correctly to determine the greater concatenated number.
Array with many duplicate numbers	The sorting algorithm should maintain its stability and produce the correct order even with numerous duplicates.
Extremely large input array impacting sorting algorithm efficiency	Use an efficient sorting algorithm such as merge sort or quicksort (or a variation optimized for strings) to maintain reasonable performance.
Concatenation resulting in a number that starts with a zero other than 0 itself	The final result string should be trimmed if it consists of leading zeros after concatenation, unless the overall result is '0'.

Empty input array

How to Handle:

Return an empty string or throw an exception, depending on requirements, as no concatenation is possible.

Input array with a single element

How to Handle:

Return the single element as a string since no concatenation partner exists.

Array with large numbers causing potential integer overflow after concatenation

How to Handle:

Use string concatenation and compare the resulting strings lexicographically to avoid integer overflow issues.

Input array containing only zeros

How to Handle:

The result should be a string of zeros concatenated, sorted based on which zero gives the bigger result when placed first.

Input array contains numbers with different lengths and leading zeros

How to Handle:

String comparison must handle the leading zeros and variable lengths correctly to determine the greater concatenated number.

Array with many duplicate numbers

How to Handle:

The sorting algorithm should maintain its stability and produce the correct order even with numerous duplicates.

Extremely large input array impacting sorting algorithm efficiency

How to Handle:

Use an efficient sorting algorithm such as merge sort or quicksort (or a variation optimized for strings) to maintain reasonable performance.

Concatenation resulting in a number that starts with a zero other than 0 itself

How to Handle:

The final result string should be trimmed if it consists of leading zeros after concatenation, unless the overall result is '0'.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Are negative numbers allowed?
If no two numbers can be concatenated to form a larger number than any other concatenation, what should be returned? (e.g., an empty string, null, or a specific error code)?
Are there any constraints on the size of the integer array?
If concatenating A+B and B+A result in the same number, which ordering should be preferred?
Is the input guaranteed to contain valid integers, or could there be null values or other unexpected data types?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take all the numbers you have.
Generate every single possible order in which you can arrange these numbers. For example, if you have two numbers, you try Number 1 followed by Number 2, and then Number 2 followed by Number 1.
For each of these orders, take the first two numbers and join them together to form a single larger number.
Compare this larger number to the number you would get if you joined the numbers in the opposite order.
Keep track of which way of joining the numbers results in the bigger combined number.
Do this for all possible pairs of numbers in all the different orders you created in the second step.
After doing this for every possible combination of numbers in every possible order, find the biggest combined number you encountered. This is the solution.

Code Implementation

def find_maximum_number_by_binary_concatenation(numbers):
    from itertools import permutations

    maximum_combined_number = ""

    # Generate all possible permutations of the input numbers.
    for permutation in permutations(numbers):
        
        for first_index in range(len(permutation)):
            for second_index in range(first_index + 1, len(permutation)):

                #Create a pair for concatenation
                first_number = str(permutation[first_index])
                second_number = str(permutation[second_index])

                combined_number_one = first_number + second_number
                combined_number_two = second_number + first_number

                # Compare which concatenation is larger.
                if combined_number_one > combined_number_two:
                    larger_combined_number = combined_number_one
                else:
                    larger_combined_number = combined_number_two

                #Update largest number found so far.
                if larger_combined_number > maximum_combined_number:
                    maximum_combined_number = larger_combined_number
    
    return maximum_combined_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, understand that simply sorting the numbers from largest to smallest doesn't work. For example, 9 and 95: 959 is smaller than 995.
The key is to compare two numbers by placing them next to each other in both possible orders. For instance, compare combining Number A then Number B versus combining Number B then Number A.
Decide which order makes a larger number. Use this comparison to sort all the numbers.
Once the numbers are in the correct order, just string them together to form the final largest possible number.

Code Implementation

def find_maximum_number_by_concatentation(number_list):

    # Custom comparison for sorting
    def compare_numbers(number1, number2):
        string1 = str(number1) + str(number2)
        string2 = str(number2) + str(number1)
        
        if string1 > string2:
            return -1
        elif string1 < string2:
            return 1
        else:
            return 0

    # Sort the numbers using custom comparison
    sorted_numbers = sorted(number_list, key=cmp_to_key(compare_numbers))

    # Combine numbers to get maximum number
    maximum_number = ''.join(map(str, sorted_numbers))
    return maximum_number

from functools import cmp_to_key

# We need a custom comparison function for sorting.
# Standard sorting won't work in this case.

# After sorting, concatenate into a single string.

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty string or throw an exception, depending on requirements, as no concatenation is possible.
Input array with a single element	Return the single element as a string since no concatenation partner exists.
Array with large numbers causing potential integer overflow after concatenation	Use string concatenation and compare the resulting strings lexicographically to avoid integer overflow issues.
Input array containing only zeros	The result should be a string of zeros concatenated, sorted based on which zero gives the bigger result when placed first.
Input array contains numbers with different lengths and leading zeros	String comparison must handle the leading zeros and variable lengths correctly to determine the greater concatenated number.
Array with many duplicate numbers	The sorting algorithm should maintain its stability and produce the correct order even with numerous duplicates.
Extremely large input array impacting sorting algorithm efficiency	Use an efficient sorting algorithm such as merge sort or quicksort (or a variation optimized for strings) to maintain reasonable performance.
Concatenation resulting in a number that starts with a zero other than 0 itself	The final result string should be trimmed if it consists of leading zeros after concatenation, unless the overall result is '0'.

Empty input array

How to Handle:

Return an empty string or throw an exception, depending on requirements, as no concatenation is possible.

Input array with a single element

How to Handle:

Return the single element as a string since no concatenation partner exists.

Array with large numbers causing potential integer overflow after concatenation

How to Handle:

Use string concatenation and compare the resulting strings lexicographically to avoid integer overflow issues.

Input array containing only zeros

How to Handle:

The result should be a string of zeros concatenated, sorted based on which zero gives the bigger result when placed first.

Input array contains numbers with different lengths and leading zeros

How to Handle:

String comparison must handle the leading zeros and variable lengths correctly to determine the greater concatenated number.

Array with many duplicate numbers

How to Handle:

The sorting algorithm should maintain its stability and produce the correct order even with numerous duplicates.

Extremely large input array impacting sorting algorithm efficiency

How to Handle:

Use an efficient sorting algorithm such as merge sort or quicksort (or a variation optimized for strings) to maintain reasonable performance.

Concatenation resulting in a number that starts with a zero other than 0 itself

How to Handle:

The final result string should be trimmed if it consists of leading zeros after concatenation, unless the overall result is '0'.