Super Ugly Number
Super ugly numbers: จำนวนบวกที่ prime factors ทั้งหมดอยู่ใน primes array ที่กำหนด
เช่น primes = [2,7,13,19] -> sequence: 1,2,4,7,8,13,14,16,19,26,28,32...
ตัวอย่างโค้ด
const num = 7;
const arr = [2, 7, 14, 19];
const superUgly = (num = 1, arr = []) => {
arr.sort((a, b) => a - b);
const ptr = [];
const res = [];
for (let i = 0; i < arr.length; i++) {
ptr[i] = 0;
}
res.push(1);
for (let i = 1; i < num; i++) {
let mn = Math.pow(2, 32) - 1;
for (let j = 0; j < arr.length; j++) {
mn = Math.min(mn, arr[j] * res[ptr[j]]);
}
res[i] = mn;
for (let j = 0; j < arr.length; j++) {
if (mn % arr[j] === 0) {
ptr[j]++;
}
}
}
return res[num - 1];
};
console.log(superUgly(num, arr));
ผลลัพธ์
16
คำอธิบาย
Multiple pointers approach: ptr[j] ชี้ index ใน res ที่จะคูณกับ arr[j] ครั้งต่อไป
แต่ละรอบหา min ของ arr[j] * res[ptr[j]] ทุก j
เพิ่ม min เข้า res, เพิ่ม ptr[j] ทุกตัวที่ผลคูณ == min (กัน duplicate)
Time: O(n * k) k = primes.length, Space: O(n + k)
LeetCode 313 Super Ugly Number
หมายเหตุ: ตัวอย่าง primes มี 14 ซึ่งไม่ใช่ prime จริงๆ ควรเป็น [2,7,13,19]
