Ugly Numbers (เลข醜 - ตัวเลขที่เฉพาะตัวประกอบเป็น 2,3,5)

Ugly Numbers คือจำนวนเต็มบวกที่ **เฉพาะตัวประกอบ (Prime Factors) มีแค่ 2, 3, 5 เท่านั้น**

ลำดับ Ugly Numbers: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, ...

หมายเหตุ: 1 ถือว่าเป็น Ugly Number (ไม่มีเฉพาะตัวประกอบ)

ตัวอย่าง Input และ Output

Input: n = 10
Output: 10th Ugly number is: 12

อัลกอริทึม Dynamic Programming (3 Pointers)

ฟังก์ชัน getUglyNumbers(n)

แนวคิด: Merge 3 Sorted Lists

Ugly Numbers ทุกตัว สร้างได้จาก Ugly Number ก่อนหน้า × 2, ×3, หรือ ×5

จัดเป็น 3 ลำดับที่เรียงแล้ว: - List2: 1×2, 2×2, 3×2, 4×2, 5×2, 6×2, 8×2, ... - List3: 1×3, 2×3, 3×3, 4×3, 5×3, 6×3, ... - List5: 1×5, 2×5, 3×5, 4×5, 5×5, ...

Merge 3 ลิสต์นี้ (ลบซ้ำ) = Ugly Numbers

ขั้นตอน (3 Pointers):

1. ugly[0] = 1, i2=i3=i5=0
2. next2=2, next3=3, next5=5
3. for i = 1 ถึง n-1:
   • next = min(next2, next3, next5)
   • ugly[i] = next
   • ถ้า next == next2: i2++; next2 = ugly[i2]*2
   • ถ้า next == next3: i3++; next3 = ugly[i3]*3
   • ถ้า next == next5: i5++; next5 = ugly[i5]*5
   • (ใช้ if แยก ไม่ใช่ else-if เพราะอาจเท่ากันได้หลายค่า)
4. คืน next (ค่า Ugly ที่ n)

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

int getUglyNum(int n) {
    int ugly[n];
    int i2 = 0, i3 = 0, i5 = 0;
    int next2 = 2, next3 = 3, next5 = 5;
    int next = 1;
    ugly[0] = 1;

    for (int i = 1; i < n; i++) {
        next = min({next2, next3, next5});
        ugly[i] = next;
        if (next == next2) { i2++; next2 = ugly[i2] * 2; }
        if (next == next3) { i3++; next3 = ugly[i3] * 3; }
        if (next == next5) { i5++; next5 = ugly[i5] * 5; }
    }
    return next;
}

int main() {
    int n;
    cout << "Enter term: "; cin >> n;
    cout << n << "th Ugly number is: " << getUglyNum(n) << endl;
    return 0;
}

Output

Enter term: 10
10th Ugly number is: 12

ความซับซ้อน

• Time: O(n)
• Space: O(n)

Super Ugly Numbers (การขยาย)

Given k primes, หาเลขที่มีเฉพาะตัวประกอบจาก k ตัวนี้ → ใช้ k pointers แทน 3

การประยุกต์

Ugly Numbers ใช้ใน Hash Table sizing, Memory Allocation, และ Computer Graphics