Problem Description

You are given a positive integer n.

Your task is to find the maximum product that can be obtained by multiplying any two digits from n.

Key points to understand:

• You need to select exactly two digits from the number n
• These two digits can be the same value if that digit appears multiple times in n
• You want to maximize the product of these two digits

For example:

• If n = 234, the digits are 2, 3, and 4. The maximum product would be 3 × 4 = 12
• If n = 944, the digits are 9, 4, and 4. The maximum product would be 9 × 4 = 36
• If n = 99, the digits are 9 and 9. The maximum product would be 9 × 9 = 81

The solution approach tracks the two largest digits encountered while processing the number. By multiplying the largest and second-largest digits, we guarantee the maximum possible product.

Intuition

To maximize the product of two digits, we need to multiply the largest possible values. Think about it: if we have digits like 2, 5, and 8, the product 8 × 5 = 40 will always be larger than 8 × 2 = 16 or 5 × 2 = 10.

This leads us to a key insight: we need to find the two largest digits in the number. The product of the two largest digits will give us the maximum possible product.

But how do we efficiently find these two largest digits? We could extract all digits, sort them, and pick the top two. However, that requires extra space and sorting overhead.

A more elegant approach is to maintain just two variables as we scan through the digits:

• a: tracks the largest digit seen so far
• b: tracks the second-largest digit seen so far

As we extract each digit from n (using divmod(n, 10) to get the last digit), we update these two variables:

• If the current digit is larger than a, it becomes our new largest. The old largest a becomes our second-largest b
• Otherwise, if the current digit is larger than b but not a, it becomes our new second-largest

This way, after processing all digits, a and b will hold the two largest digits, and a × b gives us our answer. The beauty of this approach is that it processes the number in a single pass with constant space complexity.

Learn more about Math and Sorting patterns.

Solution Approach

We implement the solution by maintaining two variables to track the largest and second-largest digits as we process the number:

Step 1: Initialize tracking variables

• Set a = 0 to track the largest digit
• Set b = 0 to track the second-largest digit

Step 2: Extract and process each digit We use a while loop to process digits from right to left:

while n:
    n, x = divmod(n, 10)

The divmod(n, 10) operation gives us:

• x: the last digit of n (remainder when divided by 10)
• n: the number with the last digit removed (quotient when divided by 10)

Step 3: Update the two largest digits For each extracted digit x, we compare and update our tracking variables:

if a < x:
    a, b = x, a  # x becomes new largest, old largest becomes second-largest
elif b < x:
    b = x        # x becomes new second-largest

The logic here is:

• If x is larger than our current largest a, then x becomes the new largest, and the old largest a gets demoted to second-largest b
• Otherwise, if x is larger than our second-largest b (but not larger than a), it becomes the new second-largest
• If x is smaller than both a and b, we don't update anything

Step 4: Return the maximum product After processing all digits, we return a * b, which gives us the product of the two largest digits.

Example walkthrough with n = 234:

• Initially: a = 0, b = 0
• Extract 4: a = 4, b = 0
• Extract 3: Since 3 < 4 but 3 > 0, b = 3
• Extract 2: Since 2 < 4 and 2 < 3, no change
• Result: a * b = 4 * 3 = 12

This approach runs in O(log n) time (number of digits) with O(1) space complexity.

Example Walkthrough

Let's walk through the solution with n = 7389:

Initial State:

• a = 0 (will track largest digit)
• b = 0 (will track second-largest digit)

Step 1: Extract digit 9

• divmod(738, 10) gives us n = 738, x = 9
• Since 9 > a (0), we update: a = 9, b = 0
• Current state: a = 9, b = 0

Step 2: Extract digit 8

• divmod(73, 10) gives us n = 73, x = 8
• Since 8 < a (9) but 8 > b (0), we update: b = 8
• Current state: a = 9, b = 8

Step 3: Extract digit 3

• divmod(7, 10) gives us n = 7, x = 3
• Since 3 < a (9) and 3 < b (8), no updates needed
• Current state: a = 9, b = 8

Step 4: Extract digit 7

• divmod(0, 10) gives us n = 0, x = 7
• Since 7 < a (9) and 7 < b (8), no updates needed
• Current state: a = 9, b = 8

Final Result:

• The two largest digits are a = 9 and b = 8
• Maximum product = 9 × 8 = 72

This demonstrates how the algorithm efficiently tracks the two largest digits in a single pass through the number, ensuring we find the maximum possible product.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the input number. This is because the while loop iterates through each digit of the number n. The number of digits in n is ⌊log₁₀(n)⌋ + 1, which is proportional to log n. In each iteration, the algorithm performs a constant amount of work using the divmod operation and comparisons.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables a, b, and x, regardless of the size of the input n. No additional data structures that grow with the input size are used.

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

Common Pitfalls

Pitfall 1: Handling Single-Digit Numbers

Issue: The algorithm assumes there are at least two digits to multiply. For single-digit numbers (n < 10), the second_largest remains 0, resulting in a product of 0.

Example:

• Input: n = 7
• Result: 7 * 0 = 0 (incorrect - should handle this edge case)

Solution: Add a check for single-digit numbers:

def maxProduct(self, n: int) -> int:
    if n < 10:
        return 0  # or handle according to problem requirements
  
    largest = 0
    second_largest = 0
    # ... rest of the code

Pitfall 2: Not Considering Duplicate Digits

Issue: Developers might mistakenly think they need to track unique digits only, but the problem allows using the same digit value twice if it appears multiple times.

Example:

• Input: n = 99
• Incorrect approach: Trying to find two different digit values
• Correct result: 9 * 9 = 81 (using the digit 9 twice)

Solution: The current algorithm handles this correctly by updating second_largest even when the digit equals largest:

elif current_digit >= second_largest:  # Use >= instead of just >
    second_largest = current_digit

Pitfall 3: Integer Overflow in Other Languages

Issue: While Python handles large integers automatically, implementing this in languages like Java or C++ might cause overflow for very large products.

Example:

• Two 9s would give 81 (safe)
• But in general multiplication problems, this could be an issue

Solution: For other languages, ensure the return type can handle the maximum possible product (9 * 9 = 81 for single digits):

// Java example
public int maxProduct(int n) {
    // Use int since max product is 81
    return largest * secondLargest;
}

Pitfall 4: Misunderstanding the Update Logic

Issue: The simultaneous assignment a, b = x, a might be confusing, leading to incorrect sequential updates.

Incorrect approach:

if current_digit > largest:
    second_largest = largest  # Update second_largest first
    largest = current_digit   # Then update largest

Correct approach (alternative clear version):

if current_digit > largest:
    temp = largest
    largest = current_digit
    second_largest = temp

Or use the tuple assignment as in the original solution for cleaner code.