my question is listed below please find answer

Question

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

Answer 1

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)

Answer 2

https://sololearn.com/compiler-playground/cwoO1Y4iVUOu/?ref=app

Answer 3

You just create a recursive function with a base case.

Answer 4

Bob_Li yes... a question of offset. but finally I can easily calculate f(1000.000)

Answer 5

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

Answer 6

Bob_Li Ohh... I planned to do it today, but.... No need! Thanks a lot!

Answer 7

Oma Falk
but isn't f(0)=1 and f(4) =29?

Answer 8

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

Answer 9

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

Answer 10

Jan nice😁. This one I can understand. j is not really necessary, I think. see my comment on your code.

Answer 11

https://sololearn.com/compiler-playground/chT2DYxMeIH7/?ref=app

Answer 12

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

Answer 13

Bob_Li I have already removed it.

Answer 14

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

Answer 15

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.

Answer 16

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.

Answer 17

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/