Given a number n, find number of digits in n’th Fibonacci Numbers. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
Examples:
Input : n = 6
Output : 1
6'th Fibonacci number is 8 and it has
1 digit.
Input : n = 12
Output : 3
12'th Fibonacci number is 144 and it has
3 digits.
A simple solution is to find n’th Fibonacci Number and then count number of digits in it. This solution may lead to overflow problems for large values of n.
A direct way is to count number of digits in the nth Fibonacci number using below Binet’s Formula.
fib(n) = (Φn - Ψ-n) / √5
where
Φ = (1 + √5) / 2
Ψ = (1 - √5) / 2
The above formula can be simplified,
fib(n) = round(Φn / √5)
Here round function indicates nearest integer.
Count of digits in Fib(n) = Log10Fib(n)
= Log10(Φn / √5)
= n*Log10(Φ) - Log10√5
= n*Log10(Φ) - (Log105)/2
As mentioned in this G-Fact, this formula doesn’t seem to work and produce correct Fibonacci numbers due to limitations of floating point arithmetic. However, it looks viable to use this formula to find count of digits in n’th Fibonacci number.
Below is the implementation of above idea :
C++
/* C++ program to find number of digits in nth Fibonacci number */#include<bits/stdc++.h>using namespace std;// This function returns the number of digits// in nth Fibonacci number after ceiling it// Formula used (n * log(phi) - (log 5) / 2)long long numberOfDigits(long long n){ if (n == 1) return 1; // using phi = 1.6180339887498948 long double d = (n * log10(1.6180339887498948)) - ((log10(5)) / 2); return ceil(d);}// Driver program to test the above functionint main(){ long long i; for (i = 1; i <= 10; i++) cout << "Number of Digits in F(" << i <<") - " << numberOfDigits(i) << "\n"; return 0;} |
Java
// Java program to find number of digits in nth// Fibonacci numberclass GFG { // This function returns the number of digits // in nth Fibonacci number after ceiling it // Formula used (n * log(phi) - (log 5) / 2) static double numberOfDigits(double n) { if (n == 1) return 1; // using phi = 1.6180339887498948 double d = (n * Math.log10(1.6180339887498948)) - ((Math.log10(5)) / 2); return Math.ceil(d); } // Driver code public static void main (String[] args) { double i; for (i = 1; i <= 10; i++) System.out.println("Number of Digits in F("+i+") - " +numberOfDigits(i)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python program to find # number of digits in nth # Fibonacci numberimport math# storing value of # golden ratio aka phiphi = (1 + 5**.5) / 2# function to find number # of digits in F(n) This # function returns the number # of digitsin nth Fibonacci # number after ceiling it# Formula used (n * log(phi) - # (log 5) / 2)def numberOfDig (n) : if n == 1 : return 1 return math.ceil((n * math.log10(phi) - .5 * math.log10(5)))// Driver Codefor i in range(1, 11) : print("Number of Digits in F(" + str(i) + ") - " + str(numberOfDig(i)))# This code is contributed by SujanDutta |
C#
// C# program to find number of // digits in nth Fibonacci numberusing System;class GFG { // This function returns the number of digits // in nth Fibonacci number after ceiling it // Formula used (n * log(phi) - (log 5) / 2) static double numberOfDigits(double n) { if (n == 1) return 1; // using phi = 1.6180339887498948 double d = (n * Math.Log10(1.6180339887498948)) - ((Math.Log10(5)) / 2); return Math.Ceiling(d); } // Driver code public static void Main () { double i; for (i = 1; i <= 10; i++) Console.WriteLine("Number of Digits in F("+ i +") - " + numberOfDigits(i)); }}// This code is contributed by Nitin Mittal. |
Javascript
<script>// Javascript program to find number of// digits in nth Fibonacci number// This function returns the// number of digits in nth// Fibonacci number after// ceiling it Formula used// (n * log(phi) - (log 5) / 2)function numberOfDigits(n){ if (n == 1) return 1; // using phi = 1.6180339887498948 let d = (n * Math.log10(1.6180339887498948)) - ((Math.log10(5)) / 2); return Math.ceil(d);} // Driver Code let i; for (let i = 1; i <= 10; i++) document.write(`Number of Digits in F(${i}) - ${numberOfDigits(i)} <br>`);// This code is contributed by _saurabh_jaiswal</script> |
PHP
<?php// PHP program to find number of // digits in nth Fibonacci number // This function returns the// number of digits in nth// Fibonacci number after // ceiling it Formula used // (n * log(phi) - (log 5) / 2)function numberOfDigits($n){ if ($n == 1) return 1; // using phi = 1.6180339887498948 $d = ($n * log10(1.6180339887498948)) - ((log10(5)) / 2); return ceil($d);} // Driver Code $i; for ($i = 1; $i <= 10; $i++) echo "Number of Digits in F($i) - " , numberOfDigits($i), "\n";// This code is contributed by nitin mittal?> |
Output
Number of Digits in F(1) - 1 Number of Digits in F(2) - 1 Number of Digits in F(3) - 1 Number of Digits in F(4) - 1 Number of Digits in F(5) - 1 Number of Digits in F(6) - 1 Number of Digits in F(7) - 2 Number of Digits in F(8) - 2 Number of Digits in F(9) - 2 Number of Digits in F(10) - 2
Time Complexity: O(1)
Auxiliary Space: O(1)
Another Approach(Using fact that Fibonacci numbers are periodic):
Fibonacci sequence is periodic modulo any integer, with period equal to 60 (known as Pisano’s period). This means that we can calculate the nth Fibonacci number modulo 10^k for some large k, and then use the periodicity to compute the number of digits. For example, we can compute F_n modulo 10^10 and count the number of digits:
F_n_mod = F_n % 10**10
digits = floor(log10(F_n_mod)) + 1
Below is the implementation of above approach:
C++
#include<bits/stdc++.h>using namespace std;long long numberOfDigits(long long n){ int k = 10; // module 10^k int phi = (1 + sqrt(5)) / 2; //golden ratio // compute the n-th Fibonacci number modulo 10^k int a = 0, b = 1; for (int i = 2; i <= n; i++) { int c = (a + b) % int(pow(10, k)); a = b; b = c; } int F_n_mod = b; // compute the number of digits in F_n_mod int digits = 1; while (F_n_mod >= 10) { F_n_mod /= 10; digits++; } return digits;}int main(){ long long i; for (i = 1; i <= 10; i++) cout << "Number of Digits in F(" << i <<") - " << numberOfDigits(i) << "\n"; return 0;}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
import java.util.*;public class GFG { public static long numberOfDigits(long n) { int k = 10; // module 10^k double phi = (1 + Math.sqrt(5)) / 2; //golden ratio // compute the n-th Fibonacci number modulo 10^k int a = 0, b = 1; for (int i = 2; i <= n; i++) { int c = (a + b) % (int) Math.pow(10, k); a = b; b = c; } int F_n_mod = b; // compute the number of digits in F_n_mod int digits = 1; while (F_n_mod >= 10) { F_n_mod /= 10; digits++; } return digits; } public static void main(String[] args) { long i; for (i = 1; i <= 10; i++) System.out.println("Number of Digits in F(" + i + ") - " + numberOfDigits(i)); }} |
Python3
import mathdef numberOfDigits(n): k = 10 # Golden ratio (approximately 1.618033988749895) phi = (1 + math.sqrt(5)) / 2 # Compute the n-th Fibonacci number modulo 10^k a, b = 0, 1 # Start the loop from 2, as we already have F(0) and F(1) for i in range(2, n + 1): c = (a + b) % pow(10, k) # Update the previous Fibonacci numbers for the next iteration a = b b = c F_n_mod = b # Compute the number of digits in F_n_mod # Initialize the digit counter to 1 (as any number has at least one digit) digits = 1 # Keep dividing F_n_mod by 10 until it becomes less than 10 while F_n_mod >= 10: F_n_mod = F_n_mod // 10 # Increment the digit counter digits += 1# Return the number of digits in the n-th Fibonacci number modulo 10^k return digits# Driver codefor i in range(1, 11): # Calculate and print the number of digits in F(i) modulo 10^10 print("Number of Digits in F(" + str(i) + ") - " + str(numberOfDigits(i)))# THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System;class GFG{ static int NumberOfDigits(long n) { int k = 10; // modulo 10^k // Compute the n-th Fibonacci number modulo 10^k int a = 0, b = 1; for (int i = 2; i <= n; i++) { int c = (a + b) % (int)Math.Pow(10, k); a = b; b = c; } int F_n_mod = b; // Compute the number of digits in F_n_mod int digits = 1; while (F_n_mod >= 10) { F_n_mod /= 10; digits++; } return digits; } static void Main(string[] args) { for (long i = 1; i <= 10; i++) { Console.WriteLine($"Number of Digits in F({i}) - {NumberOfDigits(i)}"); } }} |
Javascript
function numberOfDigits(n) { let k = 10; // module 10^k let phi = (1 + Math.sqrt(5)) / 2; // golden ratio // compute the n-th Fibonacci number modulo 10^k let a = 0, b = 1; for (let i = 2; i <= n; i++) { let c = (a + b) % Math.pow(10, k); a = b; b = c; } let F_n_mod = b; // compute the number of digits in F_n_mod let digits = 1; while (F_n_mod >= 10) { F_n_mod = Math.floor(F_n_mod / 10); digits++; } return digits;}// main functionlet i;for (i = 1; i <= 10; i++) console.log("Number of Digits in F(" + i + ") - " + numberOfDigits(i));// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Output
Number of Digits in F(1) - 1 Number of Digits in F(2) - 1 Number of Digits in F(3) - 1 Number of Digits in F(4) - 1 Number of Digits in F(5) - 1 Number of Digits in F(6) - 1 Number of Digits in F(7) - 2 Number of Digits in F(8) - 2 Number of Digits in F(9) - 2 Number of Digits in F(10) - 2
Time Complexity: O(nk)
Auxiliary Space: O(1)
References:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number
This article is contributed by Ayush Khanduri. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
