Count how many numbers containing number 4 among the numbers 1 to 8900?

Question

I Got a Problem like this "Count how many numbers containing number 4 among the numbers 1 to 8900 ?" what is the appropriate formula to solve the problem above, I tried to solve it by creating a looping algorithm as below

function iscontain($contain, $string){
    $return  = false;
    $address = 0;
    while($string{$address} !== ""){
        if(substr($string, $address, strlen($contain)) == $contain){
            $return = true;
            break;
        }
        $address++;
    }
    return $return; }
    $amount = 0;
    for($i = 1; $i <= 10000; $i++){
        if(iscontain("14", (string) $i)){
            echo $i."<br />\n";
            $amount++;
    }
}
echo "<br />";
echo $amount;

the problem is looping algorithms have limitations, if the rate is above 10 billion, it will influence computer performance.

Answer 1

How many numbers between $1$ to $N$ that does not contains $4$? This can be computed in $O(\log N)$. Subtract this from $N$.

Answer 2

Use the method of inclusion/exclusion on the first two digits:

4B[CD] give 10[00] numbers

A4[CD] + 9[00] numbers (no 94CD)

44[CD] - 1[00] numbers to prevent counting these twice.

On the last two digits, we get 19 possibilities.

So in total, we get 18*100 + 19*90 - 18*19 = 3168

Edit: Hmm. Which doesn't seem right. A different way of counting would be to count all possible combinations of [0..35..8][0..35..9]^3 and subtract that from 8900 which results in 3797.