Faced such a task:

Each new element of the Fibonacci sequence is obtained by adding the previous two. Starting from 1 and 2, we get the first 10 elements: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all even elements of the Fibonacci sequence whose sequence number is less than A and return the sum from the function all its numbers.

Example: A = 10
Fibonacci series: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Even elements: 2, 8, 34
Their sum: 44, and the sum of all its numbers - 8.

It seemed easy and began to solve this way:

<?php function solution($X) { $arr = array(1, 2); $sum = 0; $len = 0; for ($i = 2; $i <= $X; $i++) { array_push($arr, $arr[$i - 1] + $arr[$i - 2]); if ((($arr[$i - 1]) % 2) == 0 && ($i - 1) < $X) { $sum += $arr[$i - 1]; } } while ($sum != 0 && $sum > 0) { $len += $sum % 10; $sum = intval($sum / 10); } return $len; } print solution(10);

If during the check you specify 10 ( solution(10) ), then the answer is correct, if you specify a number that is greater than 90, then the answer is always 0.

The question itself is this. Where am I wrong?

    1 answer 1

    Eh can not just leave a comment. But there is no error in the algorithm, there are just limitations. The division operation modulo $a % $b in php accepts integer operands, and if this operation is applied to double-precision floating point numbers, these numbers are first converted to integers (by dropping the fractional part). But int variables have a maximum value of 9E18 .

    http://php.net/manual/ru/language.types.integer.php#language.types.integer.overflow

    And under the condition in '90' of the elements $sum = 1.2188452050948E+19 . And its cast to type int gives 0 .

    • Tell me, how can I avoid going beyond int ? - Amandi
    • @Artem google "php long arithmetic". Look and decide, but you need it, the limit of 90 is not enough. And by the way, I didn’t understand why you use an array in the algorithm. enough to store only the last 2 numbers ... - Mike
    • @Mike when I studied the algorithms, when finding Fibonacci numbers, I recommended using an array. The tasks that I found on the certification.mail.ru website took 30,000 as a result check. - Amandi
    • @Artem, let's roughly calculate, the length of 30.000 numbers will be 10.000 decimal places (sooo roughly after 2 ^ N). Addition is done by the length of the number, always 30.000 additions, multiplied by 10.000 the total length of 300 million. In any compiled language, I’m sure I’ll be in time. On php I do not know, I did not actively use it. But I think more than real - pavel