সমস্যা বিবরণ
দুটি পূর্ণসংখ্যা N এবং k দেওয়া আছে। আমাদের কাজ হল N-এর k-তম ছোট ভাজক (divisor) বের করা।
উদাহরণ
ইনপুট: N=15, k=3 আউটপুট: 5 ব্যাখ্যা: 15-এর ভাজক: 1,3,5,15 → ৩য়টি 5।
পদ্ধতি ১: সকল ভাজক সংগ্রহ + সর্ট (O(√N log N))
√N পর্যন্ত লুপ করে ভাজক জোড়া (i, N/i) সংগ্রহ করে সর্ট করে k-তমটি নেওয়া।
পদ্ধতি ২: দুটি সর্টেড অ্যারে (O(√N)) - অপ্টিমাইজড
ছোট ভাজকগুলো আর্ডারেই রাখা, বড় ভাজকগুলো ডিসেন্ডিং অর্ডারে রাখা। k ছোট হলে প্রথম অ্যারে থেকে, বড় হলে দ্বিতীয় অ্যারে থেকে নেওয়া।
#include <bits/stdc++.h>
using namespace std;
void findKthDivisor(int n,int k){
vector<int> small, large;
for(int i=1;i*i<=n;i++)
if(n%i==0){
small.push_back(i);
if(i!=n/i) large.push_back(n/i);
}
reverse(large.begin(), large.end());
vector<int> all = small;
all.insert(all.end(), large.begin(), large.end());
if(k > all.size()) cout << "Doesn't Exist";
else cout << all[k-1];
}
আউটপুট
3-th smallest divisor of 16 is 4
