title: Count the number of Ks between 0 and N
body: <h1>Problem:</h1>
  <p>I have seen questions like:</p>
  <ol>
  <li><a href="https://stackoverflow.com/questions/11891984/count-the-number-of-occurrences-of-0s-in-integers-from-1-to-n"><code>count the number of 0s between 0 and N?</code></a></li>
  <li><a href="https://math.stackexchange.com/questions/47477/number-of-occurrences-of-the-digit-1-in-the-numbers-from-0-to-n"><code>count the number of 1s between 0 and N?</code></a></li>
  <li><a href="https://sites.google.com/site/spaceofjameschen/home/recursion/compute-number-of-2s-in-a-range-of-0-n" rel="noreferrer"><code>count the number of 2s between 0 and N?</code></a></li>
  <li>... ...</li>
  </ol>
  <p>These kinds of questions are very similar of asking to find the total number that <code>Ks (i.e. K=0,1,2,...,9)</code> are shown in number range <code>[0, N]</code>.</p>
  <p>Example:</p>
  <ul>
  <li>Input:  <code>K=2, N=35</code></li>
  <li>Output: <code>14</code></li>
  <li>Detail: list of <code>2</code>s between <code>[0,35]</code>: <code>2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32</code>, note that <code>22</code> will be counted as twice (as <code>22</code> contains two <code>2</code>s)</li>
  </ul>
  <hr />
  <h1>What we have:</h1>
  <p>There are solutions for each of them (available if you search for it). Usually, <code>O(log N)</code> time is needed to solve such questions by recursively taking the highest digit into consideration, and so on. One example of counting the number of 2s between 0 and N can be solved by the following procedure (borrowed from <a href="http://tianrunhe.wordpress.com/2012/06/04/count-the-number-of-2s-between-0-and-n/" rel="noreferrer">here</a>):</p>
  <pre><code>// Take n = 319 as example =&gt; 162
  int numberOf2sBetween0AndN(int n) 
  {
      if (n &lt; 2)
          return 0;
  
      int result = 0;
      int power10 = 1;
      while (power10 * 10 &lt; n)
          power10 *= 10;
  
      // power10 = 100
      int msb = n / power10; // 3
      int reminder = n % power10; // 19
  
      /*** Count # of 2s from MSB ***/
      if (msb &gt; 2)    // This counts the first 2 from 200 to 299
          result += power10;
      if (msb == 2)   // If n = 219, this counts the first 2 from 200 to 219 (20 of 2s).
          result += reminder + 1;
  
      /*** Count # of 2s from reminder ***/
      // This (recursively) counts for # of 2s from 1 to 100; msb = 3, so we need to multiply by that.
      result += msb * numberOf2s(power10);
      // This (recursively) counts for # of 2s from 1 to reminder
      result += numberOf2s(reminder);
  
      return result;
  }
  </code></pre>
  <hr />
  <h1>Question:</h1>
  <p>Note that, we cannot simply change all <code>2</code>s part in the above code to <code>1</code>s in order to solve the problem of counting the number of <code>1</code>s between <code>0</code> and <code>N</code>. It seems that we have to handle differently (not trivial) for different cases.</p>
  <p><em><strong>Is there a general procedure we can follow to handle all <code>K</code>s (i.e. <code>K=0,1,2,...,9</code>), i.e. something like the following function?</strong></em></p>
  <pre><code>int numberOfKsBetween0AndN(int k, int n) 
  </code></pre>
  <hr />
  <h1>Test cases:</h1>
  <p>Here are some test cases if you want to check your solution:</p>
  <ul>
  <li><code>k=1, N=1</code>: 1</li>
  <li><code>k=1, N=5</code>: 1</li>
  <li><code>k=1, N=10</code>: 2</li>
  <li><code>k=1, N=55</code>: 16</li>
  <li><code>k=1, N=99</code>: 20</li>
  <li><code>k=1, N=10000</code>: 4001</li>
  <li><code>k=1, N=21345</code>: 18821</li>
  <li><code>k=2, N=10</code>: 1</li>
  <li><code>k=2, N=100</code>: 20</li>
  <li><code>k=2, N=1000</code>: 300</li>
  <li><code>k=2, N=2000</code>: 601</li>
  <li><code>k=2, N=2145</code>: 781</li>
  <li><code>k=2, N=3000</code>: 1900</li>
  </ul>