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
My Solution
We keep track of the two largest digits as we extract the digits of n. As we extract the digits, if the current digit is larger than the largest, we update the second largest to be the previous largest and we update the largest to be the digit we just encountered. If current digit is not larger than the largest so far, we check to see if it is larger than the second largest so far. Otherwise we perform no updates and move onto the next digit. Finally we return the product of the two largest integers at the end.
Time complexity would be O(log n) since we keep dividing by 10 to extract the digits. Space complexity would be O(1) since we only require constant extra space for the two largest numbers.
class Solution {
public int maxProduct(int n) {
int num1 = 0;
int num2 = 0;
while (n > 0) {
int digit = n % 10;
if (digit > num1) {
num2 = num1;
num1 = digit;
}
else if (digit > num2) {
num2 = digit;
}
n /= 10;
}
return (num1 * num2);
}
}