 # Create a method that counts a number

As usual, initially, we try to solve the task bluntly.

/* Count the number ‘2’ between 0 and n */

int numberOf2sInRange(int n) {

int count = 0;

for (int i = 2; i <= n; i++) { // We can begin with 2

count += numberOf2s(i);

}

return count;

}

/* count the number ‘2’ in a single digit */

int numberOf2s(int n) {

int count = 0;

while (n > 0) {

if (n % 10 == 2) {

count++;

}

n = n / 10;

}

return count;

}

The only interesting thing in this algorithm is transferring numberOf2s into a separate method. It is made for the code cleanness.

## Improved Solution

The idea is to look at the problem digit by digit. Picture a sequence of numbers:

0  1 2  3 4 5  6 7 8 9

10 11 12 13 14 15 16 17 18 19

20 21 22 23 24 25 26 27 28 29

……

110 111 112 113 114 115 116 117 118 119

We know that roughly one-tenth of the time, the last digit will be a 2 since it happens once in any sequence of ten numbers. In fact, any digit is a 2 roughly one-tenth of the time.

We say “roughly” because there are (very common) boundary conditions. For example, between 1 and 100, the 10’s digit is a 2 exactly 1/10th of the time. However, between 1 and 37, the 10’s digit is 2 much more than 1/10th of the time.

We can work out what exactly the ratio is by looking at the three cases individually: digit 2.

Case digits < 2

Consider the value x = 61523 and digit at index d = 3 (here indexes are considered from right and rightmost index is 0). We observe that x[d] = 1. There are 2s at the 3rd digit in the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999, and 52000 – 52999. So there are 6000 2’s total in the 3rd digit. This is the same amount as if we were just counting all the 2s in the 3rd digit between 1 and 60000.

In other words, we can round down to the nearest 10d+1, and then divide by 10, to compute the number of 2s in the d-th digit.

if x[d) < 2: count2sinRangeAtDigit(x, d) =

Compute y = round down to nearest 10d+1

return y/10

Case digit > 2

Now, let’s look at the case where d-th digit (from right) of x is greater than 2 (x[d] > 2). We can apply almost the exact same logic to see that there are the same number of 2s in the 3rd digit in the range 0 – 63525 as there as in the range 0 – 70000. So, rather than rounding down, we round up.

if x[d) > 2: count2sinRangeAtDigit(x, d) =

Compute y = round down to nearest 10d+1

return y / 10

Case digit = 2

The final case may be the trickiest, but it follows from the earlier logic. Consider x = 62523 and d = 3. We know that there are the same ranges of 2s from before (that is, the ranges 2000 – 2999, 12000 – 12999,…, 52000 – 52999). How many appear in the 3rd digit in the final, partial range from 62000 – 62523? Well, that should be pretty easy. It’s just 524 (62000, 62001, … , 62523).

if x[d] = 2: count2sinRangeAtDigit(x, d) =

Compute y = round down to nearest 10d+1

Compute z = right side of x (i.e., x%  10d)

return y/10 + z + 1

Now, all we need is to iterate through each digit in the number. Implementing this code is reasonably straightforward.

Below is the implementation of the idea.

filter_none

edit

play_arrow

brightness_4

// C++ program to count 2s from 0 to n

#include <bits/stdc++.h>

using namespace std;

// Counts the number of 2s

// in a number at d-th digit

int count2sinRangeAtDigit(int number, int d)

int powerOf10 = (int)pow(10, d);

int nextPowerOf10 = powerOf10 * 10;

int right = number % powerOf10;

int roundDown = number – number % nextPowerOf10;

int roundup = roundDown + nextPowerOf10;

int digit = (number / powerOf10) % 10;

// if the digit in spot digit is

if (digit < 2)

return roundDown / 10;

if (digit == 2)

return roundDown / 10 + right + 1;

return roundup / 10;

// Counts the number of ‘2’ digits between 0 and n

int numberOf2sinRange(int number)

// Convert integer to String

// to find its length

stringstream convert;

convert << number;

string s = convert.str();

int len = s.length();

// Traverse every digit and

// count for every digit

int count = 0;

for (int digit = 0; digit < len; digit++)

count += count2sinRangeAtDigit(number, digit);

return count;

// Driver Code

int main()

cout << numberOf2sinRange(22) << endl;

cout << numberOf2sinRange(100);

return 0;

}

This task requires detailed testing. You need to make sure you know all the boundary cases and you have checked each of them.