625. Minimum Factorization
Problem Description
The problem is to find the smallest positive integer (x
) that can be formed such that the product of all its digits equals a given positive integer (num
). For instance, if num
is 18, x
could be 29 (since 2 * 9 = 18). We want to find the smallest such x
if it exists. However, there are a couple of constraints: if x
does not exist or it is not a 32-bit signed integer (which means x
must be less than 2^31), the function should return 0.
Intuition
To find the smallest integer x
meeting our criteria, we need to consider a couple of key observations:
- To minimize
x
, we should try to use the largest digits possible (except for 0 and 1 since they don't change the product). Hence, we should start checking from 9 down to 2. - Digits must multiply to
num
, so we'll repeatedly dividenum
by these digits, ensuring divisibility at each step. - We build
x
by appending digits to its right, meaning we first find the highest place-value digit and then move towards the lower ones.
The approach works by iterating from 9 to 2 and checking if num
can be evenly divided by these digits. When it can, the digit divides num
, and itself is added to what will become x
. This process repeats until num
is reduced to 1 (if it can't be reduced to 1, x
is not possible under the problem constraints). After each division, we scale x
up by a factor of 10 (to push previously added digits leftward) before adding the new digit. In the end, x
must be within the 32-bit signed integer range, or else we return 0.
Solution Approach
The implementation follows the intuition closely and uses a straightforward iterative method, with primary focus on the following steps:
-
Early return for numbers less than 2: Given that our smallest possible positive integer that is not
1
must consist of multiple digits, the cases wherenum
is0
or1
are special. The function returns thenum
itself since no multiplication is needed.if num < 2: return num
-
Initializing variables:
ans
is initialized to0
- it will hold the answer.mul
is set to1
and is our multiplying factor which helps in building the integerx
from its least significant digit to the most significant digit.ans, mul = 0, 1
-
Iterating from 9 down to 2: The loop runs backwards from 9 to 2, checking at each step if
num
can be divided byi
without remainder (using the modulus operator%
).for i in range(9, 1, -1):
-
Dividing
num
by the digit if possible: Whennum
is divisible byi
, we dividenum
byi
using integer division//=
and updateans
. The new digit is placed in its correct position by the current value ofmul
.mul
is then increased by a factor of 10 to make space for the next digit.while num % i == 0: num //= i ans = mul * i + ans mul *= 10
-
Checking the final conditions: Once we break out of the loop, we check if
num
has been reduced to1
. If it's not, it means we could not fully factorizenum
using digits2-9
, sox
cannot exist under our constraints. Moreover, we verify that the answer fits into a32-bit
signed integer by comparing it to2**31 - 1
. If either condition is not met, we return0
.return ans if num < 2 and ans <= 2**31 - 1 else 0
The algorithm does not use any complex data structures, but it effectively leverages arithmetic operations and a simple for-loop to achieve the goal. This approach is efficient because it processes each digit in num
at most once and avoids unnecessary computations or storage.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using the number num = 26
. We are tasked with finding the smallest positive integer x
such that the product of its digits equals 26.
Firstly, the function would check if num
is less than 2
and would return num
itself if that's the case. Since 26
is greater than 1
, this early return doesn't get triggered.
if num < 2: return num
Then, the variables ans
and mul
are initialized:
ans, mul = 0, 1
Here, ans
will be built up to form our final number x
, and mul
is the multiplying factor which helps place the found factors into their correct positions within x
.
The loop starts at 9
and checks if num
is divisible by any number from 9
down to 2
. It proceeds as follows:
9
does not divide26
, so it moves to the next digit.8
does not divide26
, the algorithm continues to iterate.- ...
Until we reach the digit 2
:
for i in range(9, 1, -1):
2
does divide26
, leaving us with a quotient of13
(26 // 2 = 13
).
The current state of our variables is now:
num
becomes13
ans
is updated tomul * i + ans
, which is1 * 2 + 0 = 2
mul
is increased, multiplying by10
, becoming10
.
Now with num
as 13
, we continue to iterate. Our range is now exhausted since no digit between 2
to 9
divides 13
. The loop terminates.
Finally, we check:
- Is
num
now1
? No, it's13
, so we can't fully factorizenum
using digits2-9
. - Would
ans
be within a 32-bit signed integer range ifnum
was1
? We can't check this since the first condition has already failed.
Since we couldn't reduce num
to 1
by dividing by digits from 2
to 9
, x
does not exist within the problem constraints. Hence the function should return 0
.
return ans if num < 2 and ans <= 2**31 - 1 else 0
This example showed that the number 26
cannot be factorized into a product of digits between 2
and 9
, which means there is no such x
that would satisfy the problem's conditions.
Solution Implementation
1class Solution:
2 def smallestFactorization(self, num: int) -> int:
3 # If the number is less than 2, return the number itself as it's the smallest factorization
4 if num < 2:
5 return num
6
7 # Initialize the answer and the multiplier for the place value (ones, tens, etc.)
8 answer, multiplier = 0, 1
9
10 # Iterate over the digits from 9 to 2 since we want the smallest possible number after factorization
11 for i in range(9, 1, -1):
12 # While the current digit i is a factor of num
13 while num % i == 0:
14 # Divide num by i to remove this factor from num
15 num //= i
16 # Add the current digit to the answer with the correct place value
17 answer = multiplier * i + answer
18 # Increase the multiplier for the next place value (move to the left in the answer)
19 multiplier *= 10
20
21 # If num is fully factorized to 1 and the answer is within the 32-bit signed integer range, return answer
22 # Else, return 0 because a valid factorization is not possible or the answer is too big
23 return answer if num == 1 and answer <= 2**31 - 1 else 0
24
1class Solution {
2
3 // Method to find the smallest integer that has the exact same set of digits as the input number when multiplied.
4 public int smallestFactorization(int num) {
5 // If the number is less than 2, return it as the smallest factorization of numbers 0 and 1 is themselves.
6 if (num < 2) {
7 return num;
8 }
9
10 // Initialize result as a long type to avoid integer overflow.
11 long result = 0;
12 // Multiplier to place the digit at the correct position as we build the result number.
13 long multiplier = 1;
14
15 // Iterating from 9 to 2 which are the possible digits of the result.
16 for (int i = 9; i >= 2; --i) {
17 // If the current digit divides the number, we can use it in the factorization.
18 while (num % i == 0) {
19 // If so, divide the number by the digit to remove this factor from number.
20 num /= i;
21 // Append the digit to result, which is constructed from right to left.
22 result = multiplier * i + result;
23 // Increase the multiplier for the next digit.
24 multiplier *= 10;
25 }
26 }
27
28 // After we have tried all digits, num should be 1 if it was possible to factorize completely.
29 // Also, the result should fit into an integer.
30 // If these conditions hold, cast the result to integer and return it. Otherwise, return 0.
31 return num == 1 && result <= Integer.MAX_VALUE ? (int) result : 0;
32 }
33}
34
1class Solution {
2public:
3 // This function returns the smallest integer by recombining the factors of the input 'num'.
4 int smallestFactorization(int num) {
5 // If the number is less than 2, it is already the smallest factorization.
6 if (num < 2) {
7 return num;
8 }
9
10 // 'result' holds the smallest integer possible from the factorization.
11 // 'multiplier' is used to construct the 'result' from digits.
12 long long result = 0, multiplier = 1;
13
14 // Iterate from 9 to 2 to check for factors.
15 // We start from 9 because we want the smallest possible integer after factorization.
16 for (int i = 9; i >= 2; --i) {
17 // While 'i' is a factor of 'num', factor it out and build the result.
18 while (num % i == 0) {
19 num /= i;
20
21 // Add the factor to the result, adjusting the position by 'multiplier'.
22 result = multiplier * i + result;
23
24 // Increase the multiplier by 10 for the next digit.
25 multiplier *= 10;
26 }
27 }
28
29 // Check if remaining 'num' is less than 2 (fully factored into 2-9) and result fits into an int.
30 // If these conditions are not met, return 0 as specified.
31 return num < 2 && result <= INT_MAX ? static_cast<int>(result) : 0;
32 }
33};
34
1function smallestFactorization(num: number): number {
2 // If the number is less than 2, it is already the smallest factorization.
3 if (num < 2) {
4 return num;
5 }
6
7 // 'result' holds the smallest integer possible from the factorization.
8 // 'multiplier' is used to construct the 'result' from digits.
9 let result: number = 0;
10 let multiplier: number = 1;
11
12 // Iterate from 9 to 2 to check for factors.
13 // We start from 9 because we want the smallest possible integer after factorization.
14 for (let i: number = 9; i >= 2; --i) {
15 // While 'i' is a factor of 'num', factor it out and build the result.
16 while (num % i === 0) {
17 num /= i;
18
19 // Add the factor to the result, adjusting the position by 'multiplier'.
20 result = multiplier * i + result;
21
22 // Check if the result is growing beyond the range of a 32-bit integer
23 if (result > Number.MAX_SAFE_INTEGER) {
24 return 0;
25 }
26
27 // Increase the multiplier by 10 for the next digit.
28 multiplier *= 10;
29 }
30 }
31
32 // Check if remaining 'num' is less than 2 (fully factored into 2-9) and result fits within a 32-bit signed integer.
33 // If these conditions are not met, return 0 as specified.
34 return num < 2 && result <= 2**31 - 1 ? result : 0;
35}
36
Time and Space Complexity
The time complexity of the given code is O(log(num))
. This is because the while loop that reduces num
by a factor of i
will run at most O(log(num))
times. This is similar to how division works in terms of complexity while reducing the number digit by digit. Since the outer for loop is constant and only runs 8 times (from 9 to 2), it does not affect the time complexity significantly.
The space complexity of the code is O(1)
. No additional space that grows with the input size num
is used. We use a fixed number of variables (ans
, mul
, and i
) that do not depend on the size of the input num
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!