मान लीजिए हमारे पास एक संख्यात्मक स्ट्रिंग S है, और एक अन्य संख्या M है। मान लें d, S में सबसे बड़ा अंक है। हमें उन विभिन्न पूर्णांकों की संख्या ढूंढनी है जो M से अधिक नहीं हैं, जिन्हें d+1 से कम नहीं एक पूर्णांक n चुनकर और S को आधार-n संख्या के रूप में देखकर पाया जा सकता है?
उदाहरण के लिए, यदि इनपुट S = "999"; M = 1500 है, तो आउटपुट 3 होगा, क्योंकि S को आधार 10 संख्या के रूप में, हमें 999 मिलता है, आधार 11 संख्या के रूप में, हमें 1197 मिलता है, आधार 12 संख्या के रूप में, हमें 1413 मिलता है। ये तीन मान केवल वही हैं जो हम प्राप्त कर सकते हैं और 1500 से अधिक नहीं हैं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
यदि S का आकार 1 के बराबर है, तो: यदि S का संख्यात्मक मान <= M, तो: 1 वापस करें अन्यथा 0 वापस करें d := 0 S के प्रत्येक वर्ण c के लिए, करें d := d और (c - '0' का ASCII) का अधिकतम left := d right := M + 1 जब तक right - left > 1, करें: mid := (left + right) / 2 v := 0 S के प्रत्येक वर्ण c के लिए, करें यदि v > M / mid, तो: v := M + 1 अन्यथा v := v * mid + (c - '0' का ASCII) यदि v <= M, तो: left := mid अन्यथा right := mid 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
