Count Numbers That Has A 4 In It

Count Numbers That Has A 4 In It

Given a positive integer N, calculate the number of positive integers under N that has at least one digit equal to 4.

For example, given 8, return 1 since only 4 contains digit 4.

Solution

A straightforward way to solve this problem is for each number under N, check every digit of the number for digit 4. If it contains one, count it.

 private boolean contains4(int num) {  
   while (num > 3) {  
     if (num % 10 == 4) return true;  
     num /= 10;  
   }  
   return false;  
 }  
   
 public int Count4s(int num) {  
   int count = 0;  
   for (int i=4; i<num; ++i) {  
     if (contains4(i)) ++count;  
   }  
   return count;  
 }  

This algorithm runs in time O(N*k) where k is the number of digits in N.

Think about it.

When you count the numbers skipping digit 4,

• For 0-9, there is one number containing digit 4.
• Same for 10-19, 20-29, 30-39, 50-59, ..., 90-99, except 40-49. So, for 0-99, there are 19=1*9+10 numbers containing digit 4.
• Similarly, for 0-999, there are 271=19*9+100 numbers containing digit 4.
• Therefore, given a number with k digits, we have
• K_n = K_(n-1) * 9 + 10^(n-1), n>0
• For n-th digit x, count += (x < 4) ? x * K_(n-1) : (x-1) * K_(n-1) + 10^n
• For 0-th digit x, count += (x < 4) ? 0 : 1

For example,
count for 3516 is 991=3*271 + ((5-1)*19 + 100) + 1*1 + 1.

Take a look from another point of view.
To calculate the number of integers that do NOT contain digit 4, it is essentially counting in a 9-based numerical system. Then we have

K_n = 10^n - 9^n, n>0

For example,
count for 3516 is 991 = 3*(10^3 - 9^3) + ((5-1)*(10^2 - 9^2)+10^2) + 1*(10 - 9) + 1.
count for 341 is 63 = 3*(10^2 - 9^2) + (4*(10 - 9) + 2) + 0.

Now the algorithm is much simpler:

 public static int Count4s2(int num) {  
   int count = 0;  
   for (int nines = 1, tens = 1, remain=0; num>=1; num/=10, nines*=9, tens*=10) {  
     int digit = num % 10;  
     count += digit*(tens - nines);
     if (digit == 4) { // **4xx: count += xx
       count += (remain + 1);
     } else if (digit > 4) {
       count += tens;
     }
     remain += digit*tens;
   }  
   return count;  
 }  

This algorithm runs in time O(k).

If you are interested in number theories behind this, this post may be helpful for you.