Scale Engineer

Maximum Product of Two Digits

Easy
#3147Time: 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)`.
Patterns
Math
Algorithms
Sorting

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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)`.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem