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.