Số lượng nhiều nhất là N Bộ chữ số cho trước trong C ++

Giả sử chúng ta có một tập hợp các chữ số D đã được sắp xếp, một tập con không rỗng của {'1', '2', '3', '4', '5', '6', '7', '8', ' 9 '} trừ 0. Bây giờ, chúng ta sẽ viết một số số bằng các chữ số này, sử dụng mỗi chữ số bao nhiêu lần tùy thích. Vì vậy, nếu D ={'2', '3', '7'}, chúng ta có thể viết các số như '23', '771', '2372327'.

Bây giờ chúng ta phải tìm số nguyên dương có thể viết được nhỏ hơn hoặc bằng N.

Vì vậy, nếu đầu vào là D =[2,3,4,7], N =100, thì đầu ra sẽ là 20, vì các số có thể là 2, 3, 4, 7, 22, 23, 24, 27 , 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77. Tất cả các số khác đều lớn hơn 100.

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

• n:=chuyển N thành chuỗi

• sz:=size of n, ret:=0

• để khởi tạo i:=1, khi i

  • ret:=ret + (kích thước của D) ^ i

• để khởi tạo i:=0, khi i

  • hasSameNum:=false

  • cho mỗi chuỗi x trong D -

    • nếu x [0]

      • ret:=ret + (kích thước của D) ^ (sz - i - 1)

    • ngược lại khi x [0] giống với n [i] thì -

      • hasSameNum:=true

  • nếu không hasSameNum là khác 0, thì -

    • trả lại ret

• trả về ret + 1

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int atMostNGivenDigitSet(vector<string> &D, int N) {
      string n = to_string(N);
      int sz = n.size();
      int ret = 0;
      for (int i = 1; i < sz; i++) {
         ret += pow(D.size(), i);
      }
      for (int i = 0; i < sz; i++) {
         bool hasSameNum = false;
         for (string &x : D) {
            if (x[0] < n[i]) {
               ret += pow(D.size(), sz - i - 1);
            } else if (x[0] == n[i]) {
               hasSameNum = true;
            }
         }
         if (!hasSameNum)
         return ret;
      }
      return ret + 1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"2","3","4","7",};
   cout << (ob.atMostNGivenDigitSet(v, 100));
}

Đầu vào

{"2","3","4","7"}, 100

Đầu ra

20