-1

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.

Ikhsan Bahar
  • 11
  • Take a look at inclusion exclusion principle: http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

    Apply it in this case to 4 digit numbers which have 1,2,3,4 digits of "4".

     – Cupitor Nov 07 '14 at 11:23
  • thanks for respone @Cupitor, i will try to understand it.. – Ikhsan Bahar Nov 07 '14 at 11:39

2 Answers2

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$.

Irvan
  • 2,208
0

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.

Pieter21
  • 3,475