PHP for loop being way too slow with big inputs ( Digit Sum loop )

Question

Dear all I ask for your advice.

I have the following code/ for loop in PHP

$number= 123
$counter = 0;
$digitsum = 6 /* This is calculated by another function */

for($i=1;$i<=$number-1;$i++) {
if(array_sum(preg_split('//',$i)) == $digitsum){
  $counter++;
       }    
}

echo $counter; 

So basicly my loop counts how many numbers below the given number have the same Digit Sum and then displays how many there are. Even though it works perfectly with as long as 5 digit numbers and calcualtes the loops number within 1 second, I need it to work with 18 digit numbers and complete the counting within 1 second.

Is this even possible to achieve? Or should I go for some other solution ?

Answer 1

Here is a very fast solution. It still won't handle 18 digits in 1 second, but it can do the example in the answer by @Edakos (6, 12345) in only 2 ms.

function count_numbers_with_digit_sum( $sum, $max ) {
    if($sum < 0 || $max <= 0) {
        return 0;
    }
    $count = 0;
    $greatest_piece = (int) str_pad(1, strlen($max.""), "0");
    $first_digit = (int) substr($max, 0, 1);

    if( $max <= 9 && $sum <= 9 ) {
        $count++;
    }
    else {
        $count_to = max(1, ($sum > $first_digit) ? $first_digit : $sum );
        for( $i = 0; $i < $count_to; $i++ ) {
            $count += count_numbers_with_digit_sum( $sum - $i, $greatest_piece - 1 );
        }
        $count += count_numbers_with_digit_sum( $sum - $count_to, $max % $greatest_piece );
    }
    return $count;
}

$start = microtime(true);
echo count_numbers_with_digit_sum( 6, 12345);
echo "<br/>";
echo (int)((microtime(true) - $start)*1000) )." ms";

Some sample runs:

count_numbers_with_digit_sum( 9,  100    ) = 10      0 ms
count_numbers_with_digit_sum( 6,  123    ) = 10      0 ms
count_numbers_with_digit_sum( 6,  12345  ) = 130     2 ms
count_numbers_with_digit_sum( 23, 12345  ) = 530     40 ms
count_numbers_with_digit_sum( 34, 582973 ) = 13923   2287 ms
count_numbers_with_digit_sum( 9,  984930 ) = 2001    39 ms

Here's how it works. Let's call S(x,y) the number of distinct, positive integers less than or equal to y that have the sum of their digits equal to x. For example, S(3,25) = 3 (3, 12, 21). We can do the following logic. For simplicity, let's look only at x=6 and y=123, like in your original example. S will be the number of integers where we don't "use" the first (hundreds) digit, plus the number of integers where we do. The hundreds digit in this scenario has a maximum value of 1, so...

S(6,123) = S(6,99) + S(5,23)

Looking at the tens digit, we can use any value from 0 to 6, so:

S(6,99) =   S(6,9) // single digits
          + S(5,9) // 10-19
          + S(4,9) // 20-29
          + S(3,9) // 30-39
          + S(2,9) // 40-49
          + S(1,9) // 50-59
          + S(0,9) // 60

This lends itself very well to recursion. For a given y, we look at the scenarios where all the leftmost digits are 0 (i.e., not used), like S(x,9), S(x,99), S(x,999), etc., and then we look at the "maxed-out" leftmost digit. For example,

S(34, 12345) = S(34, 9999) + S(34, 999) + S(34, 99) + S(34, 9) + S(33, 2345)
             = 10          + 0          + 0         + 0        + S(33, 2345)
             = 10 + S(33, 999) + S(33, 99) + S(33, 9) + S(31, 345)
             = 10 + 0          + 0         + 0        + S(31, 345)
             = 10 + S(31, 99) + S(31, 9) + S(31, 45)
             = 10 + 0         + 0        + 0
             = 10

The function above implements this recursion. You can easily adapt this function to work with large "numbers" as string values:

function count_numbers_with_digit_sum_string( $sum, $max ) {
    return count_numbers_with_digit_sum_string_inner( $sum."", $max."" );
}

function count_numbers_with_digit_sum_string_inner( $sum, $max ) {
    if($sum < 0 || $max <= 0) {
        return 0;
    }
    $count = 0;
    $strlenmax = strlen($max);
    $strlensum = strlen($sum);
    $nines_less_than_max = (int) str_pad("", $strlenmax-1, "9");
    $first_digit = (int) substr($max, 0, 1);
    $last_two_digits_sum = (int) substr($sum, -2);

    if( $strlenmax <= 1 && $strlensum <= 1 ) {
        $count++;
    }
    else {
        $count_to = max( 1, ($strlensum > 1 || $sum > $first_digit) ? $first_digit : ( (int) $sum ) );
        for( $i = 0; $i < $count_to; $i++ ) {
            $count += count_numbers_with_digit_sum_string_inner( substr($sum, 0, -2) .($last_two_digits_sum - $i), $nines_less_than_max );
        }
        $count += count_numbers_with_digit_sum_string_inner( substr($sum, 0, -2) .($last_two_digits_sum - $count_to), substr($max, 1));
    }
    return $count;
}
$start = microtime(true);
echo count_numbers_with_digit_sum_string( 34, 12345);
echo "<br>".( (int)((microtime(true) - $start)*1000) )." ms";

This version takes about twice as long as the purely numeric version above.

You could speed this up tremendously by precalculating and caching values. As you can see above, there are lots of terms like S(x, 999), S(x,9999), etc. There are only 10 values of x (0..9) that "work" where y = 9, 19 values (0..18) that work for y = 99, 28 (0..27) for y = 999, etc. If you wanted to cache, say, 1,558 values (all combinations of S(x,y) for y in 9, 99, 999, up to 999,999,999,999,999,999), you could cut out a tremendous amount of the recursion and save a huge amount of time. With a big enough cache, I am confident you can get the times for 18-digit numbers down to one second. This would be easy to do, by building up to it (cache the 9 values, then 99, then 999, etc.). If I have time later, I will post a proof of concept.

Hope that helps!

(Edited to clarify caching calculation, fix calculation error in $count_to)

Answer 2

This should be faster because it doesn't use regex:

<?php

$number = 123;
$counter = 0;
$digitsum = 6; /* This is calculated by another function */

for($i=1;$i<=$number-1;$i++) {
    if(array_sum(str_split($i)) == $digitsum) {
        $counter++; 
    }
}

echo $counter;

Answer 3

You can try option C from the following:

Option A: (your attempt)

$number   = 12345;
$counter  = 0;
$digitsum = 6; 

$start = microtime();

for ($i = 1; $i <= $number - 1; $i++) {
    if (array_sum(preg_split('//', $i)) == $digitsum) {
        $counter++; 
    }
}

echo (int)((microtime() - $start)*1000); // ~ 42 miliseconds at writecodeonline.com

Option B: (from here)

$start = microtime();

$i = 0;
while ($i++ < $number) {
    if (array_sum(str_split($i)) == $digitsum) {
        $counter++; 
    }
}

echo (int)((microtime() - $start)*1000); // ~ 19 miliseconds at writecodeonline.com

Option C: (from here)

$start = microtime();

$i = 0;
while ($i++ < $number) {
    $sum = 0;
    $n = $i;
    do {
        $sum += $n % 10;
    } while ($sum <= $digitsum and $n = (int) $n / 10);

    if ($sum == $digitsum) {
        $counter++; 
    }
} 
echo (int)((microtime() - $start)*1000); // ~ 5 miliseconds at writecodeonline.com

Answer 4

maybe this is what you want

function foo($digits, $digitsum) {
    $sum = 0;
    if(!empty($digits)) {
        if($digitsum > 1) {
            $current = array_shift($digits);
            if(count($digits) > 0) {
                if($digitsum >= $current) {
                    $sum += foo($digits, $digitsum - $current);
                    for($i = 0; $i < $current; $i++) {
                        $sum += foo(array_fill(0, count($digits), 9), $digitsum - $i);
                    }
                } else {
                    for($i = 0; $i <= $digitsum; $i++) {
                        $sum += foo(array_fill(0, count($digits), 9), $digitsum - $i);
                    }
                }
            } elseif($current >= $digitsum) {
                $sum += 1;
            }
        } elseif($digitsum == 1) {
            $sum += count($digits);
        } else {
            $sum += 1;
        }
    }
    return $sum;
}
$number   = 123;
$digitsum = 6;

$digit = strlen($number);
$digits = str_split($number);
$counter = foo($digits, $digitsum);
var_dump($counter);