Recent Tutorials and Articles
HackerRank Solution: Fibonacci Modified
Published on: 25th May 2018

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 nth and (n+1)th terms, the (n+2)th can be computed by the following relation
Tn+2 = (Tn+1)2 + Tn

So, if the first two terms of the series are 0 and 1:
the third term = 12 + 0 = 1
fourth term = 12 + 1 = 2
fifth term = 22 + 1 = 5
... And so on.

Given three integers AB and N, such that the first two terms of the series (1st and 2nd terms) are A and Brespectively, compute the Nth 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 Nth 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.

Published on: 25th May 2018