इस समस्या में, हमें दो पूर्णांक मान N और k दिए गए हैं। हमारा काम है प्राकृतिक संख्या N का k-वां सबसे छोटा भाजक ढूंढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : N = 15, k = 3 Output : 5
स्पष्टीकरण -
Factors of 15 are 1, 3, 5, 15 3rd smallest is 5
समाधान दृष्टिकोण
समस्या का एक सरल समाधान है संख्या के गुणनखंडों को खोजना और उन्हें क्रमबद्ध तरीके से संग्रहीत करना और kth मानों को प्रिंट करना।
छँटाई के लिए, हम रूट (N) तक लूप करेंगे और जाँचेंगे कि N, i से विभाज्य है या नहीं। और i और (N/i) के मान को एक सरणी में संग्रहीत करें और इसे सॉर्ट करें। इस क्रमबद्ध सरणी से, k-th मान प्रिंट करें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors[n/2];
int j = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors[j] = i;
j++;
if (i != sqrt(n)){
factors[j] = n/i;
j++;
}
}
}
sort(factors, factors + j);
if (k > j)
cout<<"Doesn't Exist";
else
cout<<factors[k-1];
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
} आउटपुट
3-th smallest divisor of the number 16 is 4
एक और तरीका
समस्या को हल करने का एक अन्य तरीका दो सरणियों का उपयोग करना है जो क्रमबद्ध हैं।
एक भंडारण मान i, आरोही क्रम में क्रमबद्ध।
अन्य भंडारण मूल्य N/i, अवरोही क्रम में क्रमबद्ध।
हम दो सरणियों में से किसी एक के सबसे छोटे मान के रूप में kth प्राप्त करेंगे। यदि k सरणी के आकार से बड़ा है, तो यह अंतिम से दूसरे सरणी में मौजूद है।
अन्यथा यह पहली सरणी में मौजूद है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors1[n/2];
int factors2[n/2];
int f1 = 0,f2 = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors1[f1] = i;
f1++;
if (i != sqrt(n)){
factors2[f2] = n/i;
f2++;
}
}
}
if (k > (f1 + f2))
cout<<"Doesn't Exist";
else{
if(k <= f1)
cout<<factors1[f1-1];
else
cout<<factors2[k - f2 - 1];
}
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
} आउटपुट
3-th smallest divisor of the number 16 is 4