ค้นหาตัวหารน้อยที่สุดที่ k ของจำนวนธรรมชาติ N ใน C++

ในปัญหานี้ เราได้รับค่าจำนวนเต็มสองค่า N และ k งานของเราคือ หาตัวหารน้อยที่สุดที่ k ของจำนวนธรรมชาติ N .

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

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

คำอธิบาย −

Factors of 15 are 1, 3, 5, 15
3rd smallest is 5

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการค้นหาปัจจัยของตัวเลขและจัดเก็บในลักษณะที่เรียงลำดับแล้วพิมพ์ค่า kth

สำหรับการ sorting เราจะวนซ้ำจนถึง root(N) และตรวจสอบว่า N หารด้วย i ลงตัวหรือไม่ และเก็บค่าของ i และ (N/i) ไว้ในอาร์เรย์แล้วจัดเรียง จากอาร์เรย์ที่จัดเรียงนี้ ให้พิมพ์ค่าที่ k

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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 เรียงลำดับจากมากไปน้อย

เราจะพบค่าที่น้อยที่สุดลำดับที่ k จากอาร์เรย์ทั้งสองแบบ ถ้า k มากกว่าขนาดของอาร์เรย์ ค่านั้นจะแสดงอยู่ในอาร์เรย์ที่ 2 จากค่าที่แล้ว

มิฉะนั้นจะมีอยู่ในอาร์เรย์แรก

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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