HackerRank Fibonacci Modified Problem Solution

In this post, we will solve HackerRank Fibonacci Modified Problem Solution.

Function Description
Complete the fibonacciModified function in the editor below. It must return the nth number in the sequence.
fibonacciModified has the following parameter(s):

int t1: an integer
int t2: an integer
int n: the iteration to report

Returns
int: the nth number in the sequence
Note: The value of t[n] may far exceed the range of a 64-bit integer. Many submission languages have libraries that can handle such large results but, for those that don’t (e.g., C++), you will need to compensate for the size of the result.
Input Format
A single line of three space-separated integers, the values of t1, t2, and n.

Sample Input

0 1 5

Sample Output

Explanation
The first two terms of the sequence are t1 = 0 and t2 = 1, which gives us a modified Fibonacci sequence of {0, 1, 1, 2, 5, 27, …}. The 5th term is 5.

HackerRank Fibonacci Modified Problem Solution

Table of Contents

Fibonacci Modified C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    char a, b, n = 0, c;
    long long V = 1000000000;
    long long cache[21][50000];
    size_t s[21];
    
    a = getc(stdin) - '0';
    getc(stdin);
    b = getc(stdin) - '0';
    getc(stdin);
    while ((c = getc(stdin)) != '\n' && c != EOF) {
        n=n*10 + (c - '0');
    }

    cache[1][0]=a;
    s[1]=1;
    cache[2][0]=b;
    s[2]=1;

    for (size_t t=3; t<=n; t++) {
       for (size_t k=0; k < s[t-2]; k++) {
          cache[t][k]=cache[t-2][k];
       }
       for (size_t i=0; i<s[t-1]; i++) {
          long long rest=0;
          for (size_t j=0; j<s[t-1] || rest; j++) {
              rest += cache[t][i+j];
              if (j < s[t-1]) {
                  rest += cache[t-1][i] * cache[t-1][j];
              }
//             res[i+j] = sprintf("%07d",int($rest % $V));
              cache[t][i+j]= rest % V;
              rest = rest / V;
              s[t]=i+j+1;
          }
       }
//       printf(">%ld\n", t);
    }

// $cache[$n]->[-1] =~ s/^0//;

printf("%lld", cache[n][s[n]-1]);
    
for (int i = s[n] - 2; i >= 0; i--) { 
   printf("%09lld", cache[n][i]);
}
printf("\n");
    return 0;
}

Fibonacci Modified C++ solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

namespace
{
    char toChar(char d) {
        return d | 0x30;
    }
}

constexpr unsigned Base = 100;

class BigNumber
{
private:
    string m_num;

public:
    BigNumber(int num = 0);
    BigNumber(const BigNumber & other);
    BigNumber(BigNumber && other);
    BigNumber &operator+=(const BigNumber & num2);
    void swap(BigNumber &num);

    BigNumber &operator=(BigNumber num);

    friend BigNumber operator*(const BigNumber & num1, const BigNumber & num2);
    friend BigNumber operator+(BigNumber num1, const BigNumber & num2);
    friend ostream & operator<<(ostream & outstream, const BigNumber & num);

private:
    void add(const BigNumber &num, int exp);
};

BigNumber::BigNumber(int num)
{
    for (; num; num /= Base) {
        m_num.push_back(num % Base);
    }
    if (m_num.empty()) {
        m_num.push_back(0);
    }
}

BigNumber::BigNumber(const BigNumber & other)
    : m_num(other.m_num)
{ }

BigNumber::BigNumber(BigNumber && other)
    : m_num(std::move(other.m_num))
{ }

BigNumber operator*(const BigNumber & num1, const BigNumber & num2)
{
    BigNumber precomp[Base];
    for (int i = 1; i < Base; ++i) {
        precomp[i] = precomp[i - 1] + num1;
    }

    BigNumber result;
    int exp = 0;
    for_each(num2.m_num.begin(), num2.m_num.end(), [&result, &precomp, &exp](char c) {
        result.add(precomp[c], exp++);
    });
    return result;
}

void BigNumber::add(const BigNumber & num, int exp)
{
    if (exp > m_num.size()) {
        m_num.append(exp - m_num.size(), 0).append(num.m_num.begin(), num.m_num.end());
    } else {
        auto b1 = m_num.begin() + exp, e1 = m_num.end();
        auto b2 = num.m_num.begin(), e2 = num.m_num.end();

        int r = 0;
        for (; b1 != e1 && b2 != e2; ++b1, ++b2, r/= Base) {
            r += *b1 + *b2;
            *b1 = r % Base;
        }

        for (; r && b1 != e1; ++b1, r /= Base) {
            r += *b1;
            *b1 = r % Base;
        }

        for (; r && b2 != e2; ++b2, r /= Base) {
            r += *b2;
            m_num.push_back(r % Base);
        }

        if (b2 != e2) {
            m_num.append(b2, e2);
        }

        if (r) {
            m_num.push_back(r);
        }
    }
}

BigNumber &BigNumber::operator+=(const BigNumber & num2)
{
    add(num2, 0);
    return *this;
}

BigNumber operator+(BigNumber num1, const BigNumber & num2)
{
    num1.add(num2, 0);
    return num1;
}

ostream & operator<<(ostream & outstream, const BigNumber & num)
{
    string x(num.m_num.size() * 2, 0);
    for (int i = 0; i < num.m_num.size(); ++i) {
        auto d = num.m_num[i];
        x[2 * i] = toChar(d % 10);
        x[2 * i + 1] = toChar(d / 10);
    }
    if (x.back() == '0') {
        x.erase(x.size() - 1);
    }
    reverse(x.begin(), x.end());
    return outstream << x;
}

BigNumber & BigNumber::operator=(BigNumber num) {
    m_num = std::move(num.m_num);
    return *this;
}

void BigNumber::swap(BigNumber & num)
{
    m_num.swap(num.m_num);
}

int main() {
    int _a, _b, n;
    cin >> _a >> _b >> n;

    BigNumber a(_a), b(_b);
    while (n-- > 2) {
        a += b * b;
        a.swap(b);
    }

    cout << b;
    return 0;
}

Fibonacci Modified C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Numerics;
using System.Linq;

class Solution 
{
    static BigInteger Fib(BigInteger a, BigInteger b, int n)
    {
        if (n < 3)
           return n == 1 ? a : b;
        else
            return BigInteger.Pow(Fib(a, b, n - 1), 2) + Fib(a, b, n - 2);
    }
    
    static void Main(String[] args) {
        var input = Console.ReadLine().Split().Select(int.Parse).ToArray();       
        var output = Fib(input[0], input[1], input[2]);
        
        var o = new List<BigInteger>();
        var p10 = BigInteger.Pow(10, 100);
        
        while (output != 0)
        {
            o.Add(output % p10);
            output /= p10;
        }
        
        Console.Write(o[o.Count - 1]);
        var fmt = new string('0', 100);
        for (var i = o.Count - 2; i >= 0; i--)
        {
            var str = o[i].ToString();
            Console.Write("{0}{1}", fmt.Substring(0, 100 - str.Length), str);
        }
        Console.WriteLine();
        
    }
}

Fibonacci Modified Java Solution

import java.math.BigDecimal;
import java.util.Scanner;


public class FibonacciModified {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigDecimal t1 = new BigDecimal(sc.nextInt());
        BigDecimal t2 = new BigDecimal(sc.nextInt());
        int n = sc.nextInt();

        BigDecimal sum = new BigDecimal(0);
        for (int i = 3; i <= n; i++) {
            sum = t1.add(t2.multiply(t2));
            t1 = t2;
            t2 = sum;
        }
        System.out.println(sum);
        sc.close();
    }
}

Fibonacci Modified JavaScript Solution

var BigNumber = require('bignumber.js');

var modolu = 100000000;
var add = function(a,b)
{
    var carry = 0;
    var sum = Array(Math.max(a.length, b.length)).fill(0);
    for(var i = 0; i < sum.length; i++)
    {
        var nA = i < a.length ? a[i] : 0;
        var nB = i < b.length ? b[i] : 0
        var s = nA + nB + carry;
        carry = Math.floor(s / modolu);
        sum[i] = (s % modolu);
    }
    if(carry > 0)
        sum.push(carry);
    return sum;
};
var mulDigit = function(a,digit, sum, pad)
{
    if(digit === 0)
        return [0];
    var carry = 0;
    for(var i = 0; i < a.length; i++)
    {
        var s = a[i] * digit + carry;
        carry = Math.floor(s / modolu);
        sum[i+pad] = (sum[i+pad] || 0) + (s % modolu);
    }
    if(carry > 0)
        sum[i+pad] = (sum[i+pad] || 0) + carry;
};
var toStr = function(arr)
{
    if(arr.length === 0 || arr.length === 1 && arr[0] === 0)
    {
        process.stdout.write("0");
        return;
    }
    var padZero = x => String(modolu + x).slice(1);
    for(var i = arr.length - 1; i >= 0; i--)
    {
        if(i === arr.length - 1)
            process.stdout.write("" + arr[i]);
        else
            process.stdout.write(padZero(arr[i]));
    }
}
var mul = function(a,b)
{
    if(b.length > a.length)
        return mul(b,a);
    var sum = [];
    for(var i = 0; i < b.length; i++)
        mulDigit(a,b[i], sum, i);
    return sum;
};
var fibonacciSqr = function(a,b,n)
{
    a = new BigNumber(a);
    b = new BigNumber(b);
    for(var i = 3; i <= n; i++)
    {
        var sqr = b.times(b);
        var next = sqr.plus(a);
        //console.log(`${toStr(b)}^2 === ${toStr(sqr)} + ${toStr(a)} === ${toStr(next)}`);
        a = b;
        b = next;
    }
    BigNumber.config({ EXPONENTIAL_AT: 1e+9 })
    process.stdout.write(b.toDigits());
}
function processData(input) {
    input = input.split(" ");
    var a = +input[0];
    var b = +input[1];
    var n = +input[2];
    fibonacciSqr(a,b,n);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Fibonacci Modified Python Solution

import sys

def fib(first, second, number):
    for i in range(2,number):
        temp = first+(second*second)
        first=second
        second=temp
    print(second)

def main():
    input = sys.stdin.read()
    first, second, number = input.split()
    first = int(first)
    second = int(second)
    number = int(number)
    fib(first, second, number)
    
main()