Description
You are given a string num which represents a positive integer, and an integer t.
A number is called zero-free if none of its digits are 0.
Return a string representing the smallest zero-free number greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return "-1".
Example 1:
Input: num = "1234", t = 256
Output: "1488"
Explanation:
The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.
Example 2:
Input: num = "12355", t = 50
Output: "12355"
Explanation:
12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.
Example 3:
Input: num = "11111", t = 26
Output: "-1"
Explanation:
No number greater than 11111 has the product of its digits divisible by 26.
Constraints:
2 <= num.length <= 2 * 105numconsists only of digits in the range['0', '9'].numdoes not contain leading zeros.1 <= t <= 1014
Solutions
Way too complicated for breakfast.
/**
* @param {string} num
* @param {number} t
* @return {string}
*/
var smallestNumber = function (num, t) {
let temp = t;
for (let i = 2; i <= 9; i++) {
while (temp % i === 0) {
temp /= i;
}
}
if (temp > 1) {
return "-1";
}
const n = num.length;
const rem = new Array(n + 1);
rem[0] = t;
let pos = n - 1;
const numArr = num.split("");
for (let i = 0; i < n; i++) {
if (numArr[i] === "0") {
pos = i;
break;
}
rem[i + 1] = Math.floor(rem[i] / gcd(rem[i], parseInt(numArr[i])));
}
if (rem[n] === 1) {
return num;
}
for (let i = pos; i >= 0; i--) {
while (true) {
numArr[i] = String.fromCharCode(numArr[i].charCodeAt(0) + 1);
if (numArr[i] > "9") {
break;
}
let tNow = Math.floor(rem[i] / gcd(rem[i], parseInt(numArr[i])));
let k = 9;
for (let j = n - 1; j > i; j--) {
while (tNow % k !== 0) {
k--;
}
tNow = Math.floor(tNow / k);
numArr[j] = String.fromCharCode("0".charCodeAt(0) + k);
}
if (tNow === 1) {
return numArr.join("");
}
}
}
let ans = [];
let originalT = t;
for (let i = 9; i > 1; i--) {
while (originalT % i === 0) {
ans.push(String.fromCharCode("0".charCodeAt(0) + i));
originalT = Math.floor(originalT / i);
}
}
const padding = Math.max(n + 1 - ans.length, 0);
for (let i = 0; i < padding; i++) {
ans.push("1");
}
return ans.reverse().join("");
};
const gcd = (a, b) => {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
};