HackerRank Fibonacci Modified problem solution

In this HackerRank Fibonacci Modified problem solution, we have given three integers t1, t2, and n computer and print the nth term of a modified Fibonacci sequence.

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

Problem solution in Python.

def fibs(n,a,b):
    if n == 1:
        return a
    if n == 2:
        return b
    if fib[n] != 0:
        return fib[n]
    fib[n] = fibs(n-1,a,b) ** 2 + fibs(n-2,a,b)
    return fib[n]

fib =[]
fib = fib + [0] * (21)

line = input()
inp = [int(x) for x in line.split(' ')]
res = fibs(inp[2],inp[0],inp[1])
print (res)

Problem solution in Java.

import java.math.BigInteger;
import java.util.Scanner;

public class Solution{
    public static void main(String[]args){
        try(Scanner k = new Scanner(System.in)){
            String[] info = k.nextLine().split(" ");
            BigInteger[] sequence = new BigInteger[2];
            sequence[0] = new BigInteger(info[0]);
            sequence[1] = new BigInteger(info[1]);
            int N = Integer.parseInt(info[2]);

            for(int i = 2; i < N; i++){
                sequence[i % 2] =  sequence[(i + 1) % 2].multiply(sequence[(i + 1) % 2]).add(sequence[i % 2]);
            }
            System.out.println(sequence[0].max(sequence[1]));
        }
    }
}

Problem solution in C++.

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

void nextNumber(vector<int> &A, vector<int> &B, int &base){
    int N = B.size();
    vector<int> nB(2*N, 0);
    // Get B*B
    for(int ia=0; ia<N; ++ia){
        int carry = 0, pos = ia;
        for(int ib=0; ib<N; ++ib){
            int val = B[ia]*B[ib] + nB[pos] + carry;
            nB[pos] = val%base;
            carry = val/base;
            ++pos;
            /* while(pos+1<nB.size() && carry>0){
                carry += nB[pos+1];
                nB[pos+1] = carry%10;
                carry /= 10;
                ++pos;
            }*/
        }
        while(carry>0){
            nB[pos] = carry%base;
            carry /= base;
            ++pos;
        }
    }
    int carry = 0;
    for(int ia=0; ia<A.size(); ++ia){
        int val = A[ia] + nB[ia] + carry;
        nB[ia] = val%base;
        carry = val/base;
    }
    for(int ia=A.size(); ia<nB.size() && carry>0; ++ia){
        int val = nB[ia] + carry;
        nB[ia] = val%base;
        carry = val/base;
    }
    if(nB.back()==0)    nB.pop_back();
    
    A = B;
    B = nB;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int N;
    long long A, B;
    cin >> A >> B >> N;
    while(B < 1E9 && N-- > 2){
        long long tmp = B;
        B = B*B + A;
        A = tmp;
    }
    if(N==2){
        cout << B << endl;
    } else {
        vector<int> vA, vB;
        int base = 1E4;
        while(A>0){ vA.push_back(A%base); A=A/base; }
        while(B>0){ vB.push_back(B%base); B=B/base; }
        while(N-- > 2)  nextNumber(vA, vB, base);
        cout << vB.back();
        for(int ia=vB.size()-2; ia>=0; --ia){
            if(vB[ia]<10)   cout << "000";
            else if(vB[ia]<100) cout << "00";
            else if(vB[ia]<1000)    cout << "0";
            cout << vB[ia];
        }
        cout << endl;
    }
    
    return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX(x,y) x>y?x:y
#define CHUNK_SIZE 10000000

long* addBigInt(long* n1, long* n2, int l1, int l2, int* l) {
    int len = MAX(l1, l2) + 1;
    long* s = malloc(len*sizeof(long));
    long comp=0;
    for (int i=0; i<len; i++) {
        long dig1 = i<l1 ? n1[i] : 0;
        long dig2 = i<l2 ? n2[i] : 0;
        comp+=dig1+dig2;
        s[i]=comp%CHUNK_SIZE;
        comp/=CHUNK_SIZE;
    }
    if (s[len-1]==0) {
        len--;
        s=realloc(s, len*sizeof(long));
    }
    *l = len;
    return s;
}

long* mulBigInt(long* n1, long* n2, long l1, long l2, int* l) {
    int len = l1+l2;
    long* s = malloc(len*sizeof(long));
    long comp=0;
    for (int i=0; i<len; i++) {
        for (int j=0; j<=i; j++) {
            int k=i-j;
            long dig1 = j<l1 ? n1[j] : 0;
            long dig2 = k<l2 ? n2[k] : 0;
            comp+=dig1*dig2;
        }
        s[i]=comp%CHUNK_SIZE;
        comp/=CHUNK_SIZE;
    }
    if (s[len-1]==0) {
        len--;
        s=realloc(s, len*sizeof(long));
    }
    *l = len;
    return s;
}

// Complete the fibonacciModified function below.
long* fibonacciModified(int t1, int t2, int n, int* l) {
    long* n1=malloc(sizeof(long)); n1[0]=t1;
    long* n2=malloc(sizeof(long)); n2[0]=t2;
    int l1=1;
    int l2=1;
    *l = 1;
    for (int i=3; i<=n; i++) {
        long* t_n2=n2;
        int t_l2=l2;
        n2 = mulBigInt(n2, n2, l2, l2, &l2);
        n2 = addBigInt(n1, n2, l1, l2, &l2);
        n1 = t_n2;
        l1 = t_l2;
        *l = l2;
    }
    return n2;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    int t1; scanf("%d", &t1);
    int t2; scanf("%d", &t2);
    int n; scanf("%d", &n);

    int l;
    long* result = fibonacciModified(t1, t2, n, &l);

    fprintf(fptr, "%ld", result[l-1]);
    for (int i=l-2; i>=0; i--) fprintf(fptr, "%07ld", result[i]);
    fprintf(fptr, "n");

    fclose(fptr);

    return 0;
}