Maximum Product of Two Digits
EasyPrompt
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
nare[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
nare[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
nare[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
ninto 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
maxProductto 0. - Use a nested loop to consider all pairs of digits
(digits[i], digits[j]). The outer loop runs fromi = 0tosize-1, and the inner loop runs fromj = itosize-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
maxProductwith the maximum value between the currentmaxProductand the newly calculated product. - After the loops complete,
maxProductwill 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.
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.
Algorithm
- Extract all digits from the number
n. A simple way is to convertnto 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
ddigits, this would bedigits[d-1] * digits[d-2].
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize two variables,
largestandsecondLargest, to a value smaller than any possible digit, for example, -1. - Iterate through the digits of
n. This can be done efficiently using awhileloop with modulo and division operations, which avoids string conversion. - In each iteration, get the last digit using
digit = n % 10. - Compare the current
digitwithlargest:- If
digit > largest, it means we've found a new largest digit. We updatesecondLargestto the oldlargestvalue, and then updatelargestto the newdigit. - Else, if
digitis not greater thanlargest, we check if it's greater thansecondLargest. Ifdigit > secondLargest, we updatesecondLargestto thisdigit.
- If
- After the comparison, remove the last digit from
nby performing integer division:n = n / 10. - Repeat until
nbecomes 0. - After the loop,
largestandsecondLargestwill hold the two largest digits. The result is their product.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 * bVideo 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.