หา K-th Smallest Divisor ของ N ใน C++

ในปัญหานี้ เราได้รับ N และ K งานคือหา K-th smallest divisor (ตัวหาร) ของ N

ตัวอย่าง

Input: N = 15, k = 3 Output: 5

Divisors of 15: 1, 3, 5, 15 → 3rd = 5

วิธีที่ 1: หาตัวหารทั้งหมด + Sort O(√N log N)

วน i = 1 ถึง √N ถ้า N % i == 0 เก็บ i และ N/i → sort → หา k-th

วิธีที่ 2: Two Sorted Arrays O(√N) (ไม่ต้อง Sort)

เก็บตัวหารใน 2 array ที่เรียงลำดับแล้ว:

• factors1: i (ascending) สำหรับ i ≤ √N
• factors2: N/i (descending) สำหรับ i ≤ √N

K-th smallest = factors1[k-1] ถ้า k ≤ size(factors1) มิฉะนั้น factors2[size - (k - size1)]

ตัวอย่างโค้ด (วิธีที่ 2)

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

void findKthDivisor(int n, int k) {
    vector f1, f2;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            f1.push_back(i);
            if (i != n / i) f2.push_back(n / i);
        }
    }
    reverse(f2.begin(), f2.end()); // ทำให้ f2 ascending
    
    if (k > f1.size() + f2.size()) cout << "Doesn't Exist";
    else if (k <= f1.size()) cout << f1[k - 1];
    else cout << f2[k - f1.size() - 1];
}

int main() {
    findKthDivisor(16, 3); // 4
    return 0;
}

ผลลัพธ์

3-th smallest divisor of the number 16 is 4