Số có chữ số lặp lại trong C ++

Giả sử ta có số nguyên dương N, ta phải tìm số nguyên dương nhỏ hơn hoặc bằng N có ít nhất 1 chữ số lặp lại.

Vì vậy, nếu đầu vào là 99, thì đầu ra sẽ là 9, vì chúng ta có các số như 11, 22, 33, 44, 55, 66, 77, 88, 99.

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

Xác định một hàm A (), điều này sẽ nhận m, n,
- ret:=1
- để khởi tạo i:=0, khi i
  - ret:=ret * m
  - (giảm m đi 1)
- trả lại ret
Từ phương thức chính, hãy làm như sau -
Xác định arr mảng
để khởi tạo i:=N + 1, khi i> 0, cập nhật i:=i / 10, do -
- chèn phần tử đầu tiên của arr tại chỉ mục i mod 10 vào arr
ret:=0
n:=kích thước của arr
để khởi tạo i:=1, khi i
- ret:=ret + 9 * A (9, i - 1)
Xác định một tập hợp đã truy cập
để khởi tạo i:=0, khi i
- chữ số:=arr [i]
- để khởi tạo j:=(nếu tôi giống 0 thì 1, nếu không thì 0), khi j
  - nếu j được truy cập, thì -
    - Bỏ qua phần sau, chuyển sang phần tiếp theo
  - ret:=ret + A (9 - i, n - i - 1)
- nếu chữ số được truy cập, thì -
  - Ra khỏi vòng lặp
- chèn chữ số vào đã truy cập
return N - ret

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 A(int m, int n){
      int ret = 1;
      for (int i = 0; i < n; i++) {
         ret *= m;
         m--;
      }
      return ret;
   }
   int numDupDigitsAtMostN(int N){
      vector<int> arr;
      for (int i = N + 1; i > 0; i /= 10) {
         arr.insert(arr.begin(), i % 10);
      }
      int ret = 0;
      int n = arr.size();
      for (int i = 1; i < n; i++) {
         ret += 9 * A(9, i - 1);
      }
      set<int> visited;
      for (int i = 0; i < n; i++) {
         int digit = arr[i];
         for (int j = i == 0 ? 1 : 0; j < digit; j++) {
            if (visited.count(j))
            continue;
            ret += A(9 - i, n - i - 1);
         }
         if (visited.count(digit))
         break;
         visited.insert(digit);
      }
      return N - ret;
   }
};
main(){
   Solution ob;
   cout << (ob.numDupDigitsAtMostN(99));
}

Số có chữ số lặp lại trong C ++

Ví dụ

Đầu vào

Đầu ra