Trong bài toán này, chúng ta được cho hai giá trị nguyên N và k. Nhiệm vụ của chúng ta là tìm ước số nhỏ nhất thứ k của một số tự nhiên N .
Hãy lấy một ví dụ để hiểu vấn đề,
Input : N = 15, k = 3 Output : 5
Giải thích -
Factors of 15 are 1, 3, 5, 15 3rd smallest is 5
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm các thừa số của số và lưu trữ chúng theo cách được sắp xếp và in ra các giá trị thứ k.
Để sắp xếp, chúng ta sẽ lặp lại cho đến gốc (N) và kiểm tra xem N có chia hết cho i hay không. Và lưu trữ giá trị của i và (N / i) trong một mảng và sắp xếp nó. Từ mảng đã sắp xếp này, in ra giá trị thứ k.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
3-th smallest divisor of the number 16 is 4
Một cách tiếp cận khác
Một cách tiếp cận khác để giải quyết vấn đề là sử dụng hai mảng được sắp xếp.
Một lưu trữ các giá trị i, được sắp xếp theo thứ tự tăng dần.
Các giá trị lưu trữ khác N / i, được sắp xếp theo thứ tự giảm dần.
Chúng ta sẽ tìm dạng giá trị nhỏ nhất thứ k của một trong hai mảng. Nếu k lớn hơn kích thước của mảng, nó có trong mảng thứ hai từ cuối cùng.
Nếu không, nó có trong mảng đầu tiên.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
3-th smallest divisor of the number 16 is 4