C++ प्रोग्राम यह पता लगाने के लिए कि कितने आधारों में हम M . से बड़ी संख्या का प्रतिनिधित्व नहीं कर सकते हैं

मान लीजिए कि हमारे पास एक संख्यात्मक स्ट्रिंग S है, और एक अन्य संख्या M है। मान लें कि d S में सबसे बड़ा अंक है। हमें कई अलग-अलग पूर्णांकों में खोजना होगा जो M से अधिक नहीं हैं, एक पूर्णांक n चुनकर पाया जा सकता है जो d+1 से कम नहीं है और देखकर एस आधार-एन संख्या के रूप में?

तो, अगर इनपुट एस ="999" जैसा है; एम =1500, तो आउटपुट 3 होगा, क्योंकि एस आधार 10 संख्या के रूप में, हमें 999 मिलता है, आधार 11 संख्या के रूप में, हमें 1197 मिलता है, आधार 12 संख्या के रूप में, हमें 1413 मिलता है। ये तीन मान केवल वही हैं जो हम कर सकते हैं प्राप्त करें और 1500 से अधिक न हों।

कदम

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

if size of S is same as 1, then:
   if numeric value of S <= M, then:
      return 1
   Otherwise
      return 0
d := 0
for each character c in S, do
   d := maximum of d and (c - ASCII of '0')
left := d
right := M + 1
while right - left > 1, do:
   mid := (left + right) / 2
   v := 0
   for each character c in S, do
      if v > M / mid, then:
         v := M + 1
      Otherwise
         v := v * mid + (c - ASCII of '0')
   if v <= M, then:
      left := mid
   Otherwise
      right := mid
return left - d

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;

int solve(string S, int M){
   if (S.size() == 1){
      if (stoi(S) <= M)
         return 1;
      else
         return 0;
   }
   int d = 0;
   for (char c : S)
      d = max(d, int(c - '0'));
   long left = d;
   long right = M + 1;
   while (right - left > 1){
      long mid = (left + right) / 2;
      long v = 0;
      for (char c : S){
         if (v > M / mid)
            v = M + 1;
         else
            v = v * mid + (c - '0');
      }
      if (v <= M)
         left = mid;
      else
         right = mid;
   }
   return left - d;
}
int main(){
   string S = "999";
   int M = 1500;
   cout << solve(S, M) << endl;
}

इनपुट

"999", 1500

आउटपुट

3