Jobs

Interviews

Discussions

Maximum Product of Two Digits

Easy

Asked by:

21 views

Topics:

ArraysStrings

You are given a positive integer n.

Return the maximum product of any two digits in n.

Note: You may use the same digit twice if it appears more than once in n.

Example 1:

Input: n = 31

Output: 3

Explanation:

The digits of n are [3, 1].
The possible products of any two digits are: 3 * 1 = 3.
The maximum product is 3.

Example 2:

Input: n = 22

Output: 4

Explanation:

The digits of n are [2, 2].
The possible products of any two digits are: 2 * 2 = 4.
The maximum product is 4.

Example 3:

Input: n = 124

Output: 8

Explanation:

The digits of n are [1, 2, 4].
The possible products of any two digits are: 1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8.
The maximum product is 8.

Constraints:

10 <= n <= 10⁹

Try coding it in LeetCode

Maximum Product of Two Digits

Easy

Asked by:

21 views

Topics:

ArraysStrings

You are given a positive integer n.

Return the maximum product of any two digits in n.

Note: You may use the same digit twice if it appears more than once in n.

Example 1:

Input: n = 31

Output: 3

Explanation:

The digits of n are [3, 1].
The possible products of any two digits are: 3 * 1 = 3.
The maximum product is 3.

Example 2:

Input: n = 22

Output: 4

Explanation:

The digits of n are [2, 2].
The possible products of any two digits are: 2 * 2 = 4.
The maximum product is 4.

Example 3:

Input: n = 124

Output: 8

Explanation:

The digits of n are [1, 2, 4].
The possible products of any two digits are: 1 * 2 = 2, 1 * 4 = 4, 2 * 4 = 8.
The maximum product is 8.

Constraints:

10 <= n <= 10⁹

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 data type and range of the numbers in the input? Can they be negative, zero, or floating-point numbers?
What should I return if the input contains fewer than two digits?
Are we looking for two *distinct* digits, or can the same digit be used twice (e.g., multiplying the same digit with itself)?
If there are multiple pairs of digits that result in the same maximum product, is any one of those pairs acceptable, or should I return a specific pair (e.g., the pair with the lowest indices)?
Could you please provide a few example inputs and their corresponding expected outputs?

Brute Force Solution

Approach

The goal is to find the largest result we can get by multiplying any two digits in a number. A brute force approach means we'll try out every single possible pair of digits and see which pair gives us the biggest product.

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

Look at the number and consider each digit one at a time.
For each digit, pair it with every other digit in the number to form a pair.
Multiply the digits in each pair to get a product.
Compare the product you just got with the largest product you've found so far.
If the new product is bigger, remember it as the largest product.
Keep doing this until you have compared all possible pairs of digits.
The largest product you remember is the answer.

Code Implementation

def max_product_of_two_digits_brute_force(number):
    number_string = str(number)
    max_product = 0

    # Iterate through all possible pairs of digits.
    for first_digit_index in range(len(number_string)):

        for second_digit_index in range(len(number_string)):

            # Avoid multiplying a digit by itself.
            if first_digit_index != second_digit_index:

                first_digit = int(number_string[first_digit_index])
                second_digit = int(number_string[second_digit_index])

                product = first_digit * second_digit

                # Update the maximum product if necessary.

                if product > max_product:

                    max_product = product

    return max_product

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each digit of the input number (n digits). For each digit, it compares it with every other digit in the number to find the maximum product. This means that for each of the n digits, we perform approximately n comparisons/multiplications. Therefore, the total number of operations is roughly proportional to n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The algorithm only uses a few variables to store the current digits being multiplied and the maximum product found so far. The number of these variables remains constant regardless of the number of digits N in the input number. Therefore, the auxiliary space used is constant and does not scale with the input size.

Optimal Solution

Approach

The goal is to find the two largest numbers within a list and then multiply them together. We want to avoid checking every possible pair, so we'll find the two largest numbers directly.

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

Find the largest number in the list.
Remove that largest number from the list.
Find the largest number in the remaining list (this will be the second largest number from the original list).
Multiply the two largest numbers you found together. This is your answer.

Code Implementation

def max_product_of_two_digits(number_list):
    largest_number = max(number_list)

    # Store the largest number to calculate product
    first_largest_number = largest_number

    number_list.remove(largest_number)

    # After removing the largest, remaining max is 2nd largest.
    second_largest_number = max(number_list)

    product = first_largest_number * second_largest_number
    return product

Big(O) Analysis

Time Complexity

O(n) – Finding the largest number in a list of n elements requires iterating through the entire list once, resulting in O(n) time complexity. Removing the largest number takes O(n) in the worst-case scenario if we need to shift elements to fill the gap (though this could be O(1) if we are allowed to modify the original list and don't care about order). Finding the second largest number from the remaining list also takes O(n) time. The multiplication step is O(1). Thus, the overall time complexity is dominated by the linear searches, O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The plain English explanation specifies removing the largest number from the list, implying the creation of a copy or a modified version of the input list. This modified list stores at most N-1 elements, where N is the size of the original input list. Thus, the space usage scales linearly with the input size. This results in O(N) auxiliary space.

Edge Cases

Case	How to Handle
Null input	Return 0 or throw an IllegalArgumentException if the input is null.
Input array contains only one digit	Return 0 because we need at least two digits for a product.
Input array contains only zeros	Return 0 because the product of any two zeros is zero.
Input array contains negative numbers	Handle negative numbers correctly by considering the two most negative numbers which could produce the largest positive product.
Input array contains a mix of positive, negative, and zero numbers	Consider the largest two positive numbers and the two most negative numbers, and return the largest of those two products.
Input array with integer overflow potential in multiplication	Use a larger data type (e.g., long) to store the product, or check for potential overflow before multiplication.
Large input array for performance considerations	Use an efficient algorithm (e.g., sorting or two-pass linear scan) to find the two largest and two smallest numbers.
Duplicate largest or smallest numbers present	Algorithm must correctly identify unique indices or handle duplicates appropriately to avoid selecting the same number twice.

Null input

How to Handle:

Return 0 or throw an IllegalArgumentException if the input is null.

Input array contains only one digit

How to Handle:

Return 0 because we need at least two digits for a product.

Input array contains only zeros

How to Handle:

Return 0 because the product of any two zeros is zero.

Input array contains negative numbers

How to Handle:

Handle negative numbers correctly by considering the two most negative numbers which could produce the largest positive product.

Input array contains a mix of positive, negative, and zero numbers

How to Handle:

Consider the largest two positive numbers and the two most negative numbers, and return the largest of those two products.

Input array with integer overflow potential in multiplication

How to Handle:

Use a larger data type (e.g., long) to store the product, or check for potential overflow before multiplication.

Large input array for performance considerations

How to Handle:

Use an efficient algorithm (e.g., sorting or two-pass linear scan) to find the two largest and two smallest numbers.

Duplicate largest or smallest numbers present

How to Handle:

Algorithm must correctly identify unique indices or handle duplicates appropriately to avoid selecting the same number twice.

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 data type and range of the numbers in the input? Can they be negative, zero, or floating-point numbers?
What should I return if the input contains fewer than two digits?
Are we looking for two *distinct* digits, or can the same digit be used twice (e.g., multiplying the same digit with itself)?
If there are multiple pairs of digits that result in the same maximum product, is any one of those pairs acceptable, or should I return a specific pair (e.g., the pair with the lowest indices)?
Could you please provide a few example inputs and their corresponding expected outputs?

Brute Force Solution

Approach

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

Look at the number and consider each digit one at a time.
For each digit, pair it with every other digit in the number to form a pair.
Multiply the digits in each pair to get a product.
Compare the product you just got with the largest product you've found so far.
If the new product is bigger, remember it as the largest product.
Keep doing this until you have compared all possible pairs of digits.
The largest product you remember is the answer.

Code Implementation

def max_product_of_two_digits_brute_force(number):
    number_string = str(number)
    max_product = 0

    # Iterate through all possible pairs of digits.
    for first_digit_index in range(len(number_string)):

        for second_digit_index in range(len(number_string)):

            # Avoid multiplying a digit by itself.
            if first_digit_index != second_digit_index:

                first_digit = int(number_string[first_digit_index])
                second_digit = int(number_string[second_digit_index])

                product = first_digit * second_digit

                # Update the maximum product if necessary.

                if product > max_product:

                    max_product = product

    return max_product

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to find the two largest numbers within a list and then multiply them together. We want to avoid checking every possible pair, so we'll find the two largest numbers directly.

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

Find the largest number in the list.
Remove that largest number from the list.
Find the largest number in the remaining list (this will be the second largest number from the original list).
Multiply the two largest numbers you found together. This is your answer.

Code Implementation

def max_product_of_two_digits(number_list):
    largest_number = max(number_list)

    # Store the largest number to calculate product
    first_largest_number = largest_number

    number_list.remove(largest_number)

    # After removing the largest, remaining max is 2nd largest.
    second_largest_number = max(number_list)

    product = first_largest_number * second_largest_number
    return product

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input	Return 0 or throw an IllegalArgumentException if the input is null.
Input array contains only one digit	Return 0 because we need at least two digits for a product.
Input array contains only zeros	Return 0 because the product of any two zeros is zero.
Input array contains negative numbers	Handle negative numbers correctly by considering the two most negative numbers which could produce the largest positive product.
Input array contains a mix of positive, negative, and zero numbers	Consider the largest two positive numbers and the two most negative numbers, and return the largest of those two products.
Input array with integer overflow potential in multiplication	Use a larger data type (e.g., long) to store the product, or check for potential overflow before multiplication.
Large input array for performance considerations	Use an efficient algorithm (e.g., sorting or two-pass linear scan) to find the two largest and two smallest numbers.
Duplicate largest or smallest numbers present	Algorithm must correctly identify unique indices or handle duplicates appropriately to avoid selecting the same number twice.

Null input

How to Handle:

Return 0 or throw an IllegalArgumentException if the input is null.

Input array contains only one digit

How to Handle:

Return 0 because we need at least two digits for a product.

Input array contains only zeros

How to Handle:

Return 0 because the product of any two zeros is zero.

Input array contains negative numbers

How to Handle:

Handle negative numbers correctly by considering the two most negative numbers which could produce the largest positive product.

Input array contains a mix of positive, negative, and zero numbers

How to Handle:

Consider the largest two positive numbers and the two most negative numbers, and return the largest of those two products.

Input array with integer overflow potential in multiplication

How to Handle:

Use a larger data type (e.g., long) to store the product, or check for potential overflow before multiplication.

Large input array for performance considerations

How to Handle:

Use an efficient algorithm (e.g., sorting or two-pass linear scan) to find the two largest and two smallest numbers.

Duplicate largest or smallest numbers present

How to Handle:

Algorithm must correctly identify unique indices or handle duplicates appropriately to avoid selecting the same number twice.