Recent Tutorials and Articles
    HackerRank Solution: Fibonacci Modified
    Published on: 18th July 2016

    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: 18th July 2016

    Comment Form is loading comments...