Write a method to count the number of 2s between 0 and n.
#include <iostream>
using namespace std;
// Compute number of figures
int digit_num(int n)
{
int len = 0;
if(n == 0){
return 1;
}
while(n){
len ++;
n /= 10;
}
return len;
}
// m * 10^n, m is one digit and n is num of zeros
int generate_m_with_n_zeros(int m, int n)
{
while(n > 0){
m *= 10;
n--;
}
return m;
}
// Compute 2s in the range of (0, 1 * 10^zeros
int num_2s_in_1_with_n_zeros(int nzeros)
{
if(nzeros == 1){
return 1;
}
int total = 1;
int l = 1;
while (l < nzeros){
total *= 10;
total += generate_m_with_n_zeros(1, l);
l ++;
}
return total;
}
// Compute the most significant figure
int first_figure(int n)
{
while(n / 10 != 0){
n /= 10;
}
return n;
}
// Compute the most significant figure
int num_2s(int n)
{
int total = 0;
int base = 1;
if(n < 2){
return 0;
}
else if(n <= 9)
{
return 1;
}
int l = digit_num(n);
int two_zeros = generate_m_with_n_zeros(2, l - 1);
int three_zeros = generate_m_with_n_zeros(3, l - 1);
int first = first_figure(n);
if(n >= three_zeros){
total += 10 * generate_m_with_n_zeros(1, l - 2);
}
else if(n >= two_zeros){
total += n - two_zeros + 1;
}
total += first * num_2s_in_1_with_n_zeros( l - 1);
total += num_2s(n - generate_m_with_n_zeros(first, l - 1));
return total;
}
int main(int argc, char* argv[])
{
for(int i = 1; i < 10; i++){
cout << "less than " << generate_m_with_n_zeros(1, i) << " has " << num_2s_in_1_with_n_zeros(i) << endl;
}
for(int i = 1; i < 1003; i += 39){
cout << "below " << i << " has " << num_2s(i) << endl;
}
return 0;
}
Output
less than 10 has 1
less than 100 has 20
less than 1000 has 300
less than 10000 has 4000
less than 100000 has 50000
less than 1000000 has 600000
less than 10000000 has 7000000
less than 100000000 has 80000000
less than 1000000000 has 900000000
below 1 has 0
below 40 has 14
below 79 has 18
below 118 has 22
below 157 has 36
below 196 has 40
below 235 has 90
below 274 has 133
below 313 has 162
below 352 has 176
below 391 has 179
below 430 has 193
below 469 has 197
below 508 has 201
below 547 has 215
below 586 has 219
below 625 has 229
below 664 has 237
below 703 has 241
below 742 has 255
below 781 has 258
below 820 has 263
below 859 has 276
below 898 has 280
below 937 has 294
below 976 has 298