This tutorial provides Java solution to "Fibonacci Modified" challenge of HackerRank.

# Hackerrank Challenge Details

**Problem Statement:**

A series is defined in the following manner:

Given the n^{th} and (n+1)^{th} terms, the (n+2)^{th} can be computed by the following relation

**T _{n+2} = (T_{n+1})^{2} + T_{n}**

So, if the first two terms of the series are 0 and 1:

the third term = 1^{2} + 0 = 1

fourth term = 1^{2} + 1 = 2

fifth term = 2^{2} + 1 = 5

... And so on.

Given three integers **A**, **B** and **N**, such that the first two terms of the series (1^{st} and 2^{nd} terms) are **A** and **B**respectively, compute the N^{th} term of the series.

**Input Format:**

You are given three space separated integers **A, B and N** on one line.

**Output Format:**

One integer.

This integer is the **N ^{th}** term of the given series when the first two terms are

**A**and

**B**respectively.

**Note**

- Some output may even exceed the range of 64 bit integer.

**Constraints:**

- 0 <=
**A,B**<= 2 - 3 <=
**N**<= 20

**Sample Input:**

`0 1 5`

**Sample Output:**

`5`

**Explanation:**

The first two terms of the series are 0 and 1. The fifth term is 5. How we arrive at the fifth term, is explained step by step in the introductory sections.

# Solution Details

**Java Implementation:**

```
package com.saintech.allprogtutorials.hackerrank.algos;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @author Sain Technology Solutions
*
* Solution to Problem - https://www.hackerrank.com/challenges/fibonacci-modified
*
*/
public class FibonacciModified {
/**
* Returns the modified fibonacci of a number.
*
* @param num number for which fibonacci needs to be modified
* @param fibonacciTable Map containing the number as key and its fibonacci number as value.
* @return integer representing modified fibonacci for input number.
*/
private static BigInteger modifiedFibonacci(int num, Map<Integer, BigInteger> fibonacciTable) {
// if number is present in map, it means fibonacci number has been calculated for this.
// We simply return the value from Map.
if(fibonacciTable.containsKey(num)) {
return fibonacciTable.get(num);
}
// Get the fibnacci number for num - 1 and num -2 by calling current method recursively.
final BigInteger lastNumFibonacci = modifiedFibonacci(num - 1, fibonacciTable);
final BigInteger numFibonacci = lastNumFibonacci.multiply(lastNumFibonacci).add(modifiedFibonacci(num - 2, fibonacciTable));
// Put the number and its fibonacci in Map so that it can be utilized later without having to recalculate it.
fibonacciTable.put(num, numFibonacci);
return numFibonacci;
}
public static void main(String[] args) {
final Scanner in = new Scanner(System.in);
final BigInteger A = BigInteger.valueOf(in.nextLong());
final BigInteger B = BigInteger.valueOf(in.nextLong());
// Put the A and B in Map with key 1 and 2 respectively. This map will be used to store the number and its fibonacci
// to avoid recalculation. We recognize the need of this map(table) by seeing that fibonacci values for a number are
// used multiple times. E.g. f(5) = f(4)*f(4) + f(3) and f(6) = f(5)*f(5) + f(4). As we can see both f(5) and f(6) needs f(4).
// Hence storing the values in a Map will make our algorithm run faster.
final Map<Integer, BigInteger> fibonacciTable = new HashMap<>();
fibonacciTable.put(1, A);
fibonacciTable.put(2, B);
final int N = in.nextInt();
System.out.println(modifiedFibonacci(N, fibonacciTable));
in.close();
}
}
```

Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.