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

छठा सबसे छोटा तत्व 4 है [1,2,2,3,3,4,6,6,9]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें ठीक (), इसमें m, n, x,
रिट:=0
इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
- अस्थायी:=न्यूनतम x / i और m
- रिट:=रिट + अस्थायी
रिटर्न रिटर्न
मुख्य विधि से, निम्न कार्य करें -
ret:=-1, Low :=1, high:=m * n
कम <=उच्च होने पर, −
- मध्य :=निम्न + (उच्च-निम्न)/2
- सीएनटी:=ठीक है(एम, एन, मिड)
- यदि cnt>=k, तो −
  - उच्च :=मध्य - 1
  - सेवानिवृत्त:=मध्य
- अन्यथा
  - निम्न :=मध्य + 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*”