Số chữ số một trong C ++

Giả sử chúng ta có một số n, Chúng ta phải đếm tổng số chữ số 1 xuất hiện trong tất cả các số không âm nhỏ hơn hoặc bằng n. Vì vậy, nếu đầu vào là 15, thì đầu ra sẽ là 8, vì các số chứa 1 là [1,10,11,12,13,14,15], có 8 số 1.

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

ret:=0
để khởi tạo i:=1, khi i <=n, i =i * 10 do -
- a:=n / i, b:=n mod i, x:=a mod 10
- nếu x giống với 1 thì
  - ret =ret + (a / 10) * i + (b + 1)
- Ngược lại khi x giống 0 thì -
  - ret =ret + (a / 10) * i
- Nếu không
  - ret =ret + (a / 10 + 1) * i
trả lại ret

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;
class Solution {
   public:
   int countDigitOne(int n) {
      int ret = 0;
      for(long long int i = 1; i <= n; i*= (long long int)10){
         int a = n / i;
         int b = n % i;
         int x = a % 10;
         if(x ==1){
            ret += (a / 10) * i + (b + 1);
         }
         else if(x == 0){
            ret += (a / 10) * i;
         } else {
            ret += (a / 10 + 1) *i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.countDigitOne(15));
}

Số chữ số một trong C ++

Ví dụ

Đầu vào

Đầu ra