Smallest number with given digit product
Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n, or "-1" if no such number exists.
class Solution:
def smallestNumber(self, n: int) -> str:
cnt = [0] * 10
for i in range(9, 1, -1):
while n % i == 0:
n //= i
cnt[i] += 1
if n > 1:
return "-1"
ans = "".join(str(i) * cnt[i] for i in range(2, 10))
return ans if ans else "1"class Solution {
public String smallestNumber(long n) {
int[] cnt = new int[10];
for (int i = 9; i > 1; --i) {
while (n % i == 0) {
++cnt[i];
n /= i;
}
}
if (n > 1) {
return "-1";
}
StringBuilder sb = new StringBuilder();
for (int i = 2; i < 10; ++i) {
while (cnt[i] > 0) {
sb.append(i);
--cnt[i];
}
}
String ans = sb.toString();
return ans.isEmpty() ? "1" : ans;
}
}To find the smallest positive integer whose digits' product equals nnn, we use prime factorization and a greedy approach. If nnn contains prime factors greater than 7, return "-1" as such factors can't be formed by multiplying digits 1-9. Decompose nnn using the smallest factors possible: convert as many factors of 9, then 8, down to 2. For example, decompose 18 as 9×2 instead of 3×3×2. The resulting digits are then sorted in ascending order to form the smallest number.
This approach ensures the smallest integer is found by minimizing the digit values and their counts. For instance, given n=36, decomposing into 9×4(which further splits to 3×3×2×2) and sorting yields "2233". This method efficiently handles the factorization and combination of digits, ensuring the smallest lexicographical order for the result.
Related Problems
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).