C++ program to find number of digits in Nth Fibonacci number.

Fibonacci numbers follow the sequence of adding two previous numbers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

Find the number of digits Nth Fibonacci no

If we input 3 it will give us the no of digits in 3rd Fibonacci no that is 1 similarly if we give input as 7 it will give us the no of digits in 7th Fibonacci no that is 2.

Example

Input : n = 3 
Output : 1 

Input : n = 7 
Output : 2

 

Method 1: using recursion

In recursion, we divide the problem into small problems and the call recursion for the remaining problem. In this problem recursive relation is F(n) = F(n-1) + F(n-2).Coded in C++ language.

using recursion we will find the Fibonacci digit corresponds to the given no N using function fibo. After getting the Nth Fibonacci no then using the function noodfigits we will get the no of digits present in that Nth Fibonacci no.

#include<iostream>
using namespace std;

int noofdigits(int n){
    int count=0;
    while(n){
        int x=n%10;
        n=n/10;
        count++;
    }
    return count;
}

int fibo(int n){
    //Base Case
    if(n==0 || n==1){
        return n;
    }
    // Recursive case
  int SmallProblem1 = fibo(n-1);
  int SmallProblem2 = fibo(n-2);

  //Solution
  int BigProb = SmallProblem1+SmallProblem2;

  return BigProb;
}

int main(){
    int n=7;
    int x=fibo(n);
    cout<<noofdigits(x);
}

Output

2

 

Time complexity : T(n) = T(n-1) + T(n-2) which is exponential.

Since we can observe that in the recursive approach there is a lot of repeated work so we use DP approach to optimize our code for the nth Fibonacci number.

 

Method 2: Using  Dynamic Programming 

Using Dynamic Programming both top-down and bottom-up approaches to reduce time complexity.

funtions fiboTopDown and BottomUp return the Nth Fibonacci no and then using the function noofdigits we will get the no of digits present in that Nth Fibonacci no.

#include<iostream>
using namespace std;

int noofdigits(int n){
    int count=0;
    while(n){
        int x=n%10;
        n=n/10;
        count++;
    }
    return count;
}

int fiboTopDown(int n,int *dp){
    if(n==0||n==1){
        dp[n]=n;
        return n;
    }
    if(dp[n]!=-1){
        return dp[n];
    }

    int ans=fiboTopDown(n-1,dp)+fiboTopDown(n-2,dp);
    dp[n]=ans;
    return ans;
}

int fiboBottomUp(int n){
    int *dp=new int[n+1];
    dp[0]=0;
    dp[1]=1;
    for(int i=2; i<=n; i++){
        dp[i]=dp[i-1]+dp[i-2];

    }
    return dp[n];
}

int main(){
    int n=12;
    int *dp=new int[n+1];
    for(int i=0;i<=n;i++){
        dp[i]=-1;
    }
    int x=fiboTopDown(n,dp);
    int y=fiboBottomUp(n);

    cout<<noofdigits(x)<<endl;
    cout<<noofdigits(y)<<endl;

}

Output

3
3

 

Leave a Reply

Your email address will not be published. Required fields are marked *