CODEWITHSUNDEEP
pythonalgorithmfibonaccifibonacci-heap
hack3r-0m
hack3r-0m

Reputation: 750

Finding last digit of sum from m to n Fibonacci numbers. (0 ≤ 𝑚 ≤ 𝑛 ≤ 10^14)

My code is as follow :

m, n = map(int, input().split())

# write function "fibtotal" which takes input x and gives accurate fib(x+2)%10  (as sum till fib(x) == fib(x+2) - 1)
# using above function get fibtotal(m-1) and fibtotal(n)
# subtract fibtotal(m-1) from fibtotal(n) and do mod 10 gives last digit of sum from m to n
# take care of handling large input sizes, 0 ≤ 𝑚 ≤ 𝑛 ≤ 10^14

def fibtotal(x):

  sum = 1 # if both initial conditions fail then loop starts from 2

  x= x % 60 # pisano period of 10 is 60 and to get last digit we need to divide by 10

  if x == 0:
    sum = 1 # fib(2)
    return sum 

  if x == 1:
    sum = 2 # fib(3)
    return sum

  a, b = 0, 1

  for i in range(2, x+3): # to find sum till fib(x+2)

    c = (a+b)%10
    sum += c
    a, b = b%10, c%10

  return sum%10

# no need to subtract 1 from both as they cancel out
print(fibtotal(n)-fibtotal(m-1))

Following Cases fail using this algorithm:

10 10 My output: 4, correct output: 5

10 200 My output: 5, correct output: 2

1234 12345 My output: 2, correct output: 8

(and possibly many more)

I want to know where is the problem and how can I fix it? Is there any better approach using same fundamentals?

Upvotes: 0

Views: 147

Answers (2)

hack3r-0m
hack3r-0m

Reputation: 750

As Jean-Claude mentioned above, there were two main errors

no. of times the loop run

Ideally, the loop should run x times(including conditions), but I confused it with sum(fib(0 to x)) = fib(x+2) -1 and made it run x+2 times

needless %10 at many places

The only place where mod 10 was necessary was at the last statement while displaying the final result. The cause of this error was too much focus on handling large input sizes but they were already handled doing x%60.

The same rectified code looks like:

m, n = map(int, input().split())


def fibtotal(x):

  sum = 1 # if both initial conditions fail then loop starts from 2

  x= x % 60 # pisano period of 10 is 60 and to get last digit we need to divide by 10

  if x == 0:
    sum = 1 # fib(2)
    return sum 

  if x == 1:
    sum = 2 # fib(3)
    return sum

  a, b = 0, 1

  for i in range(2, x+1): # to find sum till fib(x+2)

    c = a+b
    sum += c
    a, b = b, c

  return sum

# no need to subtract 1 from both as they cancel out
print((fibtotal(n)-fibtotal(m-1))%10)

NOTE: the value "sum" doesn't matter if m > 1 as it cancels out while subtracting at last

Upvotes: 0

user13517564
user13517564

Reputation:

There is a problem in the number of loop: you do x+1 loops where there should be x. And I don't understand why you don't start with sum = 0.

Then, you can make use of the period to compute the sum in constant time, without any loop. The aux list was computed using fibtotal1.

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

def fibtotal1(n):
    return sum(fib(k) % 10 for k in range(n + 1)) % 10

def fibtotal2(n):
    s, a, b = 0, 0, 1
    for i in range(n % 60):
        a, b = b, a + b
        s += a
    return s % 10

aux = [0, 1, 2, 4, 7, 2, 0, 3, 4, 8, 3, 2, 6, 9, 6, 6, 3, 0, 4, 5,
       0, 6, 7, 4, 2, 7, 0, 8, 9, 8, 8, 7, 6, 4, 1, 6, 8, 5, 4, 0,
       5, 6, 2, 9, 2, 2, 5, 8, 4, 3, 8, 2, 1, 4, 6, 1, 8, 0, 9, 0]

def fibtotal3(n):
    return aux[n % 60]

print(all(fibtotal1(n) == fibtotal2(n) == fibtotal3(n) for n in range(1000)))

Note also that in your last step, due to computing mod 10 the difference may be negative, so it should be:

def fibtotal(m, n):
    return (fibtotal3(n) - fibtotal3(m - 1)) % 10

For the reader passing by: fibtotal2 and fibtotal3 work because fib(n) % 10 is periodic with period 60, and the sum of the elements of the period is a multiple of 10. See Fibonacci's final digits cycle every 60 numbers on Math.SE.

Upvotes: 2

Related Questions