Chương trình C ++ để tìm trong bao nhiêu cơ số mà chúng ta có thể biểu diễn số không lớn hơn M

Giả sử chúng ta có một chuỗi số S và một số M. Gọi d là chữ số lớn nhất trong S. Chúng ta phải tìm trong nhiều số nguyên khác nhau không lớn hơn M có thể tìm được bằng cách chọn một số nguyên n không nhỏ hơn d + 1 và thấy S là số cơ số n?

Vì vậy, nếu đầu vào giống như S ="999"; M =1500, thì đầu ra sẽ là 3, bởi vì S là số cơ số 10, chúng ta nhận được 999, là số cơ sở 11, chúng ta nhận được 1197, dưới dạng số cơ sở 12, chúng ta nhận được 1413. Ba giá trị này là những giá trị duy nhất mà chúng ta có thể lấy và không lớn hơn 1500.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

"999", 1500

Đầu ra

3