โปรแกรมหา Ugly Number ลำดับที่ n ใน C++

Ugly numbers คือจำนวนที่ตัวประกอบเฉพาะ (prime factors) มีเพียง 2, 3, 5 เท่านั้น
ลำดับ Ugly numbers: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

ตัวอย่าง: n = 10 → Ugly number ลำดับที่ 10 คือ 12

แนวทางการแก้ปัญหา (Dynamic Programming O(n))

ใช้ 3 pointer (twoIdx, threeIdx, fiveIdx) ติดตามตำแหน่งที่จะคูณ 2, 3, 5 ต่อไป
ในแต่ละขั้นตอน เลือกค่า min ของ v[twoIdx]*2, v[threeIdx]*3, v[fiveIdx]*5 เป็น ugly number ถัดไป
เคลื่อน pointer ที่ตรงกับค่าที่เลือก

การนำไปใช้ (Implementation)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> v(n + 1);
        if (n == 1) return 1;
        
        int two = 2, three = 3, five = 5;
        int twoIdx = 2, threeIdx = 2, fiveIdx = 2;
        
        for (int i = 2; i <= n; i++) {
            int curr = min({two, three, five});
            v[i] = curr;
            
            if (curr == two) {
                two = v[twoIdx] * 2;
                twoIdx++;
            }
            if (curr == three) {
                three = v[threeIdx] * 3;
                threeIdx++;
            }
            if (curr == five) {
                five = v[fiveIdx] * 5;
                fiveIdx++;
            }
        }
        return v[n];
    }
};

int main() {
    Solution ob;
    cout << ob.nthUglyNumber(15);
    return 0;
}

อินพุต

15

เอาต์พุต

24

Ugly numbers 15 ตัวแรก: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24