Accenture OA-6 2024

Problem Description

Alex is exploring a series and she came across a special series in which
* f(N) = f(N-1) * f(N-1) + f(N-2) * f(N-2)
* where, f(0) = 1 and 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 Format:

• input1: An integer value N.

Output Format:

Return an integer value representing the Nth number in this special series, modulo 47.

Constraints:

• 0 ≤ N ≤ 10^9

Example

Sample Input:

N = 5

Sample Output:

18

Explanation:
Let's calculate the first few terms of the series using the given formula:

• f(0) = 1(given)
• f(1) = 1 (given)
• f(2) = f(1) * f(1) + f(0) * f(0) = 1 * 1 + 1 * 1 = 2
• f(3) = f(2) * f(2) + f(1) * f(1) = 2 * 2 + 1 * 1 = 5
• f(4) = f(3) * f(3) + f(2) * f(2) = 5 * 5 + 2 * 2 = 29
• f(5) = f(4) * f(4) + f(3) * f(3) = 29 * 29 + 5 * 5 = 878

Now, we need to calculate f(5) modulo 47.
878 mod 47 = 18

Therefore, the output for N = 5 is 18.