# Maximum Product of Two Digits
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-product-of-two-digits)
Canonical: https://scaleengineer.com/dsa/problems/maximum-product-of-two-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
---
## Problem
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 <= 109`

# Approaches
## Brute-Force with Nested Loops
This approach involves first extracting all the digits from the input number `n` and storing them in a list. Then, it uses nested loops to iterate through every possible pair of digits from this list. For each pair, it calculates their product and compares it with the maximum product found so far, updating it if the new product is larger.
**Time:** O((log n)^2). Let `d` be the number of digits in `n`, so `d` is approximately `log10(n)`. Extracting digits takes `O(d)` time. The nested loops run in `O(d^2)` time. Thus, the total time complexity is dominated by the nested loops, resulting in `O((log n)^2)`. · **Space:** O(log n). We use an auxiliary list to store the `d` digits of `n`, where `d` is the number of digits. The number of digits is proportional to `log10(n)`.
**Pros:** Simple to understand and implement.; Correctly finds the maximum product by checking all possibilities.
**Cons:** Inefficient compared to other approaches, especially if the number of digits were large. The quadratic time complexity is unnecessary.
### Explanation
To solve the problem, we can systematically check every possible pair of digits. First, we extract the digits from the number `n`, for instance, by converting it to a string and then processing each character. These digits are stored in a list. Then, we use two nested loops to iterate through all unique pairs of indices `(i, j)` where `i <= j`. For each pair, we compute the product `digits[i] * digits[j]` and update our `maxProduct` variable if this product is greater than the current maximum. This guarantees that we explore all combinations and find the maximum possible product.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxProduct(int n) {
        String s = Integer.toString(n);
        List<Integer> digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            digits.add(c - '0');
        }

        int maxProduct = 0;
        for (int i = 0; i < digits.size(); i++) {
            for (int j = i; j < digits.size(); j++) {
                int currentProduct = digits.get(i) * digits.get(j);
                if (currentProduct > maxProduct) {
                    maxProduct = currentProduct;
                }
            }
        }
        return maxProduct;
    }
}
```
### Algorithm
- Convert the input integer `n` into a string to easily access its digits.
- Create a list of integers to store the numeric value of each digit.
- Iterate through the characters of the string, convert each character to its integer equivalent, and add it to the list.
- Initialize a variable `maxProduct` to 0.
- Use a nested loop to consider all pairs of digits `(digits[i], digits[j])`. The outer loop runs from `i = 0` to `size-1`, and the inner loop runs from `j = i` to `size-1`. This ensures that we consider products of a digit with itself and all subsequent digits.
- Inside the inner loop, calculate the product of the current pair of digits.
- Update `maxProduct` with the maximum value between the current `maxProduct` and the newly calculated product.
- After the loops complete, `maxProduct` will hold the maximum product of any two digits.

## Sorting the Digits
A more efficient approach is to realize that the maximum product will always come from the two largest digits in the number. This approach extracts all digits, sorts them, and then simply multiplies the two largest digits, which will be at the end of the sorted list.
**Time:** O(log n * log(log n)). Let `d` be the number of digits, `d ≈ log10(n)`. Extracting digits takes `O(d)`. Sorting `d` digits takes `O(d log d)`. The total time complexity is `O(d + d log d) = O(d log d)`, which translates to `O(log n * log(log n))`. · **Space:** O(log n). Space is required to store the `d` digits of the number `n` in a list before sorting.
**Pros:** More efficient than the brute-force approach.; Logically straightforward: find the two largest items by sorting.
**Cons:** Sorting the entire list of digits is overkill, as we only need the top two elements.; Still requires extra space to store the digits.
### Explanation
The key insight for this method is that to maximize a product of two positive numbers, we should choose the two largest numbers available. We can apply this to the digits of `n`. The process is to first get all the digits of `n` into a collection, like a list. Then, we sort this list in ascending order. Once sorted, the two largest digits will be conveniently located at the very end of the list. We can then access these last two elements and multiply them to get the maximum product. Since the problem constraints guarantee at least two digits, we don't need to worry about index out of bounds errors.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int maxProduct(int n) {
        String s = Integer.toString(n);
        List<Integer> digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            digits.add(c - '0');
        }

        Collections.sort(digits);

        int size = digits.size();
        // The problem constraints state n >= 10, so there are at least 2 digits.
        return digits.get(size - 1) * digits.get(size - 2);
    }
}
```
### Algorithm
- Extract all digits from the number `n`. A simple way is to convert `n` to a string and then iterate through its characters.
- Store these digits in a list or an array.
- Sort the list of digits in non-decreasing (ascending) order.
- After sorting, the two largest digits will be the last two elements in the list.
- The maximum product is the product of these two elements. If the number has `d` digits, this would be `digits[d-1] * digits[d-2]`.

## Single Pass to Find Two Largest Digits
The most efficient approach is to find the two largest digits in a single pass without storing all the digits or sorting them. We can iterate through the digits of the number `n` while keeping track of the largest and second-largest digits found so far.
**Time:** O(log n). We iterate through the digits of `n` exactly once. The number of digits `d` is proportional to `log10(n)`. The work done per digit is constant. · **Space:** O(1). This approach uses only a few variables to store the largest and second-largest digits, regardless of the size of `n`. No auxiliary data structures are needed.
**Pros:** Optimal time complexity, as we must look at each digit at least once.; Optimal space complexity, using constant extra space.; Avoids overhead of string conversions or creating intermediate data structures.
**Cons:** The logic for tracking the two largest elements is slightly more complex than the other approaches, but it's a standard and highly efficient pattern.
### Explanation
This optimal solution avoids creating any intermediate data structures. We can extract digits one by one from the number `n` using the modulo operator (`% 10`) and integer division (`/ 10`). As we extract each digit, we compare it against two variables that track the `largest` and `secondLargest` digits seen so far. If the current digit is greater than `largest`, the old `largest` becomes the new `secondLargest`, and the current digit becomes the new `largest`. Otherwise, if the current digit is not the largest but is greater than `secondLargest`, it becomes the new `secondLargest`. This process continues until all digits have been processed. Finally, we multiply the values stored in `largest` and `secondLargest`.

```java
class Solution {
    public int maxProduct(int n) {
        int largest = -1;
        int secondLargest = -1;

        int tempN = n;
        if (tempN == 0) return 0; // Edge case, though constraints say n >= 10

        while (tempN > 0) {
            int digit = tempN % 10;
            if (digit > largest) {
                secondLargest = largest;
                largest = digit;
            } else if (digit > secondLargest) {
                secondLargest = digit;
            }
            tempN /= 10;
        }
        return largest * secondLargest;
    }
}
```
### Algorithm
- Initialize two variables, `largest` and `secondLargest`, to a value smaller than any possible digit, for example, -1.
- Iterate through the digits of `n`. This can be done efficiently using a `while` loop with modulo and division operations, which avoids string conversion.
- In each iteration, get the last digit using `digit = n % 10`.
- Compare the current `digit` with `largest`:
  - If `digit > largest`, it means we've found a new largest digit. We update `secondLargest` to the old `largest` value, and then update `largest` to the new `digit`.
  - Else, if `digit` is not greater than `largest`, we check if it's greater than `secondLargest`. If `digit > secondLargest`, we update `secondLargest` to this `digit`.
- After the comparison, remove the last digit from `n` by performing integer division: `n = n / 10`.
- Repeat until `n` becomes 0.
- After the loop, `largest` and `secondLargest` will hold the two largest digits. The result is their product.

# Solutions
### Java

```java
class Solution {
public
  int maxProduct(int n) {
    int a = 0, b = 0;
    for (; n > 0; n /= 10) {
      int x = n % 10;
      if (a < x) {
        b = a;
        a = x;
      } else if (b < x) {
        b = x;
      }
    }
    return a * b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProduct(int n) {
    int a = 0, b = 0;
    for (; n; n /= 10) {
      int x = n % 10;
      if (a < x) {
        b = a;
        a = x;
      } else if (b < x) {
        b = x;
      }
    }
    return a * b;
  }
};

```

### Python

```python
class Solution:
    def maxProduct(self, n: int) -> int: a = b = 0 while n: n, x = divmod(n, 10) if a < x: a, b = x, a elif b < x: b = x return a * b

```