vivek_ragi

NUMBER_OF_DIGIT_ONE

Jun 22nd, 2021
805
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int countDigitOne(int n) {
  4.         /*
  5.             2229
  6.             1029, 1000 - 1029
  7.             1 -29
  8.             1000 - 1029 - 30 1's
  9.             [1 - 999] + 0
  10.             2 * f(999) + divisor + remainder
  11.             2 * something + 1000 + 229
  12.             2200
  13.             2 * f(999) + 1000 + rem = 0;
  14.             f(9) = 1;
  15.             f(99) = 10*f(9) + 9 + 1
  16.        
  17.         */
  18.         if(n <= 0) {
  19.             return 0;
  20.         }
  21.         unordered_map<long, long> mp;
  22.         mp[9] = 1;
  23.         //9,99,999,......
  24.         for(long i = 9; i < 2 * pow(10,9); i = 10*i + 9) {
  25.             mp[10*i + 9] = 10*mp[i] + i + 1;
  26.         }
  27.         int tp = n;
  28.         int divisor = 1;
  29.         while(tp/10) {
  30.             tp/=10;
  31.             divisor *= 10;
  32.         }
  33.         int rem = n % divisor;
  34.         int ans = 0;
  35.         int first = (n/divisor);
  36.         ans = ans + first * mp[divisor-1];
  37.        
  38.         if(first > 1) {
  39.             ans += divisor;
  40.         }
  41.         if(first == 1) {
  42.             ans += rem + 1;
  43.         }
  44.         ans += countDigitOne(rem);
  45.         return ans;
  46.     }
  47. };
RAW Paste Data