মান লিখুন: আমাদের কাছে একটি সাংখ্যিক স্ট্রিং S এবং আরেকটি সংখ্যা M রয়েছে। S-তে সবচেয়ে বড় অঙ্ক হল d। d+1 বা তার চেয়ে বড় কোনো পূর্ণসংখ্যা n বেছে নিলে S কে বেস-n সংখ্যা হিসেবে দেখলে কতগুলো ভিন্ন পূর্ণসংখ্যা (যে M-র চেয়ে বড় নয়) পাওয়া যায় তা বের করতে হবে।
উদাহরণ
যদি ইনপুট হয় S = "999"; M = 1500, তবে আউটপুট হবে 3, কারণ:
বেস ১০: 999
বেস ১১: 1197
বেস ১২: 1413
এই তিনটি মানই M-র চেয়ে বড় নয়।
সমাধানের ধাপসমূহ
যদি S.size() == 1:
যদি S-এর মান <= M: 1 রিটার্ন করুন
অন্যথায়: 0 রিটার্ন করুন
d := 0
S-এর প্রতিটি ক্যারেক্টার c এর জন্য:
d := max(d, c - '0')
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')
যদি v <= M: left := mid
অন্যথায়: right := mid
left - d রিটার্ন করুন
C++ বাস্তবায়ন
#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, 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
