+ 1

my question is listed below please find answer

Problem Statement: Alex is exploring a series and she came across a special series, in which f(N)=f(N-1)*(N-1)+(N-2)*(N-2) mod 47 where f(0) = 1, f(1) = 1 Your task is to help Alex find and return an integer value, representing the Nth number in this special series Note: Return the output modulo 47. Input Specification: input1: An integer value N. Output Specification: Return an integer value, representing the Nth number in this special series. Sample Input: 4 Sample Output: 29

24th Aug 2024, 8:27 PM
vishnu bcr
vishnu bcr - avatar
17 ответов
+ 5
Well.... recuersion is nice for lower numbers but hard for let's,say 100.000. Fortunately the series is periodic. Find out period and offset and you can do it for any number. why it is periodic? Remember the pigeon-hole principle! There can't be more than 47**2 pairs as arguments for f(N)
25th Aug 2024, 6:09 AM
Oma Falk
Oma Falk - avatar
+ 3
You just create a recursive function with a base case.
24th Aug 2024, 8:59 PM
Jan
Jan - avatar
+ 3
Bob_Li yes... a question of offset. but finally I can easily calculate f(1000.000)
25th Aug 2024, 11:25 AM
Oma Falk
Oma Falk - avatar
+ 3
ok, last one, I promise. Oma Falk 's code wrapped in a function (2 actually, for efficiency)... The limit is your computer's memory. Amazing how smart analysis can actually solve a problem, not just grinding an approximation of it by brute force.😁 https://sololearn.com/compiler-playground/c05Su6wOOUmj/?ref=app
26th Aug 2024, 5:51 AM
Bob_Li
Bob_Li - avatar
+ 3
Bob_Li Ohh... I planned to do it today, but.... No need! Thanks a lot!
26th Aug 2024, 7:35 AM
Oma Falk
Oma Falk - avatar
+ 2
Oma Falk but isn't f(0)=1 and f(4) =29?
25th Aug 2024, 11:14 AM
Bob_Li
Bob_Li - avatar
+ 2
Oma Falk yes, your iteration should start at 2. 0 and 1 is already defined in your list as [1,1]. two solutions. One with recursion helped by functool.cache. The other modifed from Jan 's list append solution, which works basically the same as Oma Falk's code. https://sololearn.com/compiler-playground/c8dtTQmPG3te/?ref=app https://sololearn.com/compiler-playground/cXx6G0VqG5AI/?ref=app
25th Aug 2024, 12:32 PM
Bob_Li
Bob_Li - avatar
+ 2
I made a simpler solution to prevent the array from being filled with all the numbers. Now it only holds a maximum of three numbers during runtime. https://sololearn.com/compiler-playground/cwDdEozS64XN/?ref=app
25th Aug 2024, 3:22 PM
Jan
Jan - avatar
+ 2
Jan nice😁. This one I can understand. j is not really necessary, I think. see my comment on your code.
25th Aug 2024, 3:46 PM
Bob_Li
Bob_Li - avatar
+ 1
use 2 lists to avoid long internal list . But there doesn't seem to be any advantage in this. The single list method performs similarly or even a bit better. list len does not seem to be a bottleneck. https://sololearn.com/compiler-playground/cfAfSRVd9rg3/?ref=app
25th Aug 2024, 2:00 PM
Bob_Li
Bob_Li - avatar
+ 1
Bob_Li I have already removed it.
25th Aug 2024, 3:59 PM
Jan
Jan - avatar
+ 1
Jan I wrapped your idea in a function and simplified some more by ditching the len check. I also ended the iteration one step earlier and did the final calculation in the return statement. https://sololearn.com/compiler-playground/cWdgE4lEvbf9/?ref=app
25th Aug 2024, 4:29 PM
Bob_Li
Bob_Li - avatar
+ 1
Bob_Li The solution has become quite heavy. The array needs to be global and popped outside the function. Maybe it's better to build a solution with a class, so the function doesn't have to count from 2 to n every time it's called in another loop.
25th Aug 2024, 6:16 PM
Jan
Jan - avatar
+ 1
Jan OOP would be overkill, I think. Much like what we 3 have been doing to this post.😅 We just took the problem and over-engineered solutions for it.😁 The OP is probably flooded with solutions and refinement of solutions and we don't even know if any of these are of any help. Anyway, your method of using pop(0) to limit the list length is great, and OOP classes are just glorified functions in my mind. Storing values as list inside functions is ok. It is fun and educational for me, though. Oma Falk's deconstruction for an iterative approach and your pop(0) trick were new knowledge I picked up from this coding session.
25th Aug 2024, 9:18 PM
Bob_Li
Bob_Li - avatar
0
def find_special_series(N): # Base cases if N == 0 or N == 1: return 1 # Initialize an array to store the series values f = [0] * (N + 1) f[0] = 1 f[1] = 1 # Calculate the series values for N >= 2 for i in range(2, N + 1): f[i] = (f[i-1] * (i-1) + (i-2) * (i-2)) % 47 return f[N] # Sample Input N = 4 # Function Call print(find_special_series(N)) # Output: 29 Check out my comment and my pokemon!!! https://tutodessiner.fr/dessin-pokemon/
17th Sep 2024, 2:15 AM
Agus Tortas
Agus Tortas - avatar