Giả sử chúng ta có một số nguyên n không âm. Chúng ta phải đếm tất cả các số có chữ số duy nhất x, trong đó x nằm trong khoảng từ 0 đến 10 ^ n. Vì vậy, nếu số n là 2, thì kết quả sẽ là 91, vì chúng ta muốn tìm các số từ 0 đến 100 mà không có 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 -
-
nếu n là 0, thì trả về 1
-
n:=min of 10 and n
-
nếu n là 1, thì trả về 10
-
ans:=9 và ret:=10
-
cho tôi trong phạm vi từ 2 đến n
-
ans:=ans * (9 - i + 2)
-
ret:=ret + ans
-
-
trả lại ret
Ví dụ (C ++)
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;
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n == 0)return 1;
n = min(10, n);
if(n == 1)return 10;
int ans = 9;
int ret = 10;
for(int i = 2; i<= n; i++){
ans *= (9 - i + 2);
ret += ans;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.countNumbersWithUniqueDigits(3));
} Đầu vào
3
Đầu ra
739