Spp recursive sequence doubt

#1

getting a wrong answer , cant understand where it is going wrong

#2

@rohit_1906
Hey your code has very high time complexity upto 10^18 which makes this solution infeasible.

What you should have done is find sum of first n elements and find sum of first m - 1 elements. And subtract them to get sum of element in range(m, n). You need to find the sums using matrix exponentiation (O(logn)) time.

#3

thats exactly what i have done , using matrix exponentiation , if you have checked correctly i m calculating sum(n) in the matrix itself and then subtracting it with sum(m) , complexity is definitely not 10^18 ,

#4

please share the correct code so that i can check where i m going wrong

#5

@rohit_1906
refer to this


or even

#6

Hey @rohit_1906
You’re reopened this doubt
How can I help you ?

#7

my doubt is related to spp recursive sequence version 2 , i have attached a link of my code , its giving wrong answer for few test cases , please help me out in that and both the links provided by the previous TA are giving error , segmentation or bus error

#8

@rohit_1906
Issue is with line 76 and 88
You’re subtracting two values which were under modulo
It may happen that Sn may be less than Sm due to modulo
So while returning such result do ((Sn-Sm)%mod+mod)%mod

#9

tried correcting it still giving wrong answer ,

one thing i noticed that it gives correct answer for this particular test case if in compute function n-1 and m-1 is given as input

#10

@rohit_1906
Rest your logic was fine I don’t know where it went wrong
Try to cross verify your solution with this once

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.