C++ এ গুণিতিক সারণীতে Kth ক্ষুদ্রতম সংখ্যা

ধরুন আমরা একটি গুণের সারণী সম্পর্কে জানি। কিন্তু আমরা কি গুণ সারণী থেকে k-তম ক্ষুদ্রতম সংখ্যাটি দ্রুত বের করতে পারি? তাই যদি আমাদের একটি m * n গুণন সারণির উচ্চতা m এবং দৈর্ঘ্য n এবং একটি ধনাত্মক পূর্ণসংখ্যা k করতে হয়, তাহলে আমাদের এই টেবিলে k-তম ক্ষুদ্রতম সংখ্যাটি খুঁজে বের করতে হবে।

সুতরাং যদি m =3 এবং n =3 এবং k 6 হয়, তাহলে আউটপুট হবে 4., এর কারণ গুণন সারণী −

এর মত ৷

	1	2	3
1	1	2	3
2	2	4	6
3	3	6	9

6তম ক্ষুদ্রতম উপাদান হল 4 হিসাবে [1,2,2,3,3,4,6,6,9]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন ঠিক করুন(), এটি m, n, x,
ret :=0
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), −
- temp :=সর্বনিম্ন x / i এবং m
- ret :=ret + temp
রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
ret :=-1, low :=1, high :=m * n
যখন কম <=বেশি, কর −
- মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2
- cnt :=ঠিক আছে(m, n, mid)
- যদি cnt>=k হয়, তাহলে −
  - উচ্চ :=মধ্য - 1
  - ret :=mid
- অন্যথায়
  - নিম্ন :=মধ্য + 1
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ok(int m, int n, int x){
      int ret = 0;
      for(int i = 1; i <= n; i++){
         int temp = min(x / i, m);
         ret += temp;
      }
      return ret;
   }
   int findKthNumber(int m, int n, int k) {
      int ret = -1;
      int low = 1;
      int high = m * n ;
      while(low <= high){
         int mid = low + (high - low)/ 2;
         int cnt = ok(m, n, mid);
         if(cnt >= k){
            high = mid - 1;
            ret = mid;
         }else low = mid + 1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findKthNumber(3,3,6));
}

ইনপুট

“2*”