Digit Count in Range

Suppose we have an integer d between 0 and 9, we also have two positive integers low and high as lower and upper bounds, respectively. We have to find the number of times that d occurs as a digit in all integers between low and high, including the bounds low and high.

So, if the input is like d = 1, low = 1, high = 13, then the output will be 6, as digit d=1 occurs 6 times like 1,10,11,12,13.

To solve this, we will follow these steps −

Define a function zero(), this will take n,

• ret := 0, x := 0

• if n is same as 0, then −

  • return 1

• for initialize m := 1, when m <= n, update m := m * 10, do −

  • a := n / m

  • b := n mod m

  • z := a mod 10

  • if number of digits in m is same as number of digits in n, then −

    • Come out from the loop

  • if z > x, then −

    • ret := ret + ((a / 10) + 1)

  • otherwise when z is same as x, then

    • ret := ret + ((a / 10) * m + (b + 1))

  • Otherwise

    • ret := ret + (a / 10)

• return ret

• Define a function f(), this will take x, n,

• ret := 0

• for initialize m := 1, when m <= n, update m := m * 10, do −

  • a := n / m

  • b := n mod m

  • z := a mod 10

  • if z > x, then

    • ret := ret + ((a / 10) + 1)

  • otherwise when z is same as x, then −

    • ret := ret + ((a / 10) * m + (b + 1))

  • Otherwise

    • ret := ret + (a / 10)

  • if x is same as 0, then −

    • ret := ret - m

• return ret

• From the main method do the following

• return ret

• return f(d, high - f(d, low - 1))

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int digitCount(int x){       int ret = 0;       while (x) {          ret++;          x /= 10;       }       return ret;    }    int zero(int n){       int ret = 0;       int x = 0;       if (n == 0)       return 1;       for (int m = 1; m <= n; m *= 10) {          int a = n / m;          int b = n % m;          int z = a % 10;          if (digitCount(m) == digitCount(n))          break;          if (z > x) {             ret += ((a / 10) + 1) * m;          }          else if (z == x) {             ret += (a / 10) * m + (b + 1);          } else {             ret += (a / 10) * m;          }          cout << ret << endl;       }       return ret;    }    int f(int x, int n){       int ret = 0;       for (int m = 1; m <= n; m *= 10) {          int a = n / m;          int b = n % m;          int z = a % 10;          if (z > x) {             ret += ((a / 10) + 1) * m;          }          else if (z == x) {             ret += (a / 10) * m + (b + 1);          } else {             ret += (a / 10) * m;          }          if (x == 0) {             ret -= m;          }       }       return ret;    }    int digitsCount(int d, int low, int high){       return f(d, high) - f(d, low - 1);    } }; main(){    Solution ob;    cout << (ob.digitsCount(1,1,13)); }

Input

1,1,13

Output

6