Count Numbers That Has A 4 In It | N00tc0d3r

Count Numbers That Has A 4 In It | N00tc0d3r
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.
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.
This algorithm runs in time O(k).

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(N*k) where k is the number of digits in N.

 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;  
 }  

Read full article from Count Numbers That Has A 4 In It | N00tc0d3r