fibonacci modified

dynamic-programming
fibonacci-sequence
medium

#1

i found this question on hackerrank. can anyone explain how this can be solved using c++ .


#2

@sumesh

The basics of the solution is a simple loop. This is pseudocode…

    declare t_Nminus2 := t1  // function parameter
    declare t_Nminus1 := t2  // function parameter
    declare t_N 

    for i := 3 to n inclusive  // n is a function parameter
        t_N := t_Nminus2 + t_Nminus1 * t_Nminus1
        t_Nminus2 := t_Nminus1
        t_Nminus1 := t_N
    end for

    return t_N

The challenge isn’t the base algorithm outlined above. The challenge is the datatype to use for t_N.

Since n can be up to 20 and the next term includes the square of the prior term, the max possible value of t_N is much larger than ULLONG_MAX (largest possible unsigned long long int), as the HackerRank problem statement says. There is no native data type in C++ that can handle such large integers, so it’s possible this problem wants you to create your own datatype.


#3

exactly… but i don’t know how should i perform multiplication over my custom data type.
@sbatten1969