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.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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^9

Solution

Method 1 - Brute Force Pairwise Product

Intuition

The maximum product of two digits will always be the product of the two largest digits in the number. We can check all pairs to be sure.

Approach

  1. Convert the integer n to a list of its digits.
  2. For every pair of digits (including the same digit twice if it appears more than once), compute their product.
  3. Track the maximum product found.
  4. Return the maximum product.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxProduct(int n) {
        vector<int> d;
        while (n) {
            d.push_back(n % 10);
            n /= 10;
        }
        int ans = 0;
        for (int i = 0; i < d.size(); ++i) {
            for (int j = i; j < d.size(); ++j) {
                int prod = d[i] * d[j];
                if (prod > ans) ans = prod;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maxProduct(n int) int {
    d := []int{}
    for n > 0 {
        d = append(d, n%10)
        n /= 10
    }
    ans := 0
    for i := 0; i < len(d); i++ {
        for j := i; j < len(d); j++ {
            prod := d[i] * d[j]
            if prod > ans {
                ans = prod
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxProduct(int n) {
        List<Integer> d = new ArrayList<>();
        while (n > 0) {
            d.add(n % 10);
            n /= 10;
        }
        int ans = 0;
        for (int i = 0; i < d.size(); i++) {
            for (int j = i; j < d.size(); j++) {
                int prod = d.get(i) * d.get(j);
                if (prod > ans) ans = prod;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maxProduct(n: Int): Int {
        val d = mutableListOf<Int>()
        var x = n
        while (x > 0) {
            d.add(x % 10)
            x /= 10
        }
        var ans = 0
        for (i in d.indices) {
            for (j in i until d.size) {
                val prod = d[i] * d[j]
                if (prod > ans) ans = prod
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxProduct(self, n: int) -> int:
        d: list[int] = []
        while n > 0:
            d.append(n % 10)
            n //= 10
        ans = 0
        for i in range(len(d)):
            for j in range(i, len(d)):
                prod = d[i] * d[j]
                if prod > ans:
                    ans = prod
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn max_product(n: i32) -> i32 {
        let mut d = vec![];
        let mut x = n;
        while x > 0 {
            d.push(x % 10);
            x /= 10;
        }
        let mut ans = 0;
        for i in 0..d.len() {
            for j in i..d.len() {
                let prod = d[i] * d[j];
                if prod > ans {
                    ans = prod;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maxProduct(n: number): number {
        const d: number[] = [];
        while (n > 0) {
            d.push(n % 10);
            n = Math.floor(n / 10);
        }
        let ans = 0;
        for (let i = 0; i < d.length; i++) {
            for (let j = i; j < d.length; j++) {
                const prod = d[i] * d[j];
                if (prod > ans) ans = prod;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(k^2), where k is the number of digits in n. We check all pairs of digits.
  • 🧺 Space complexity: O(k), for storing the digits of n.