Given a number N, the task is to check if the given number and all its digits are Fibonacci. If so, then the given number is a Full Fibonacci Number, else not.
Examples:
Input: 13
Output: Yes
Explanation: 13 and its digits 1 and 3 are all Fibonacci numbersInput: 34
Output: No
Explanation: 4 is not a Fibonacci number.
Approach:
First check if all digits of N are Fibonacci or not. If so, similarly check if N is Fibonacci or not by the principle that a number is Fibonacci if and only if one or both of (5*N2 + 4) or (5*N2 – 4) is a perfect square.
Below code is the implementation of the above approach:
C++
// C++ program to check // if a given number is // a Full Fibonacci // Number or not #include <bits/stdc++.h> using namespace std; // A utility function that // returns true if x is // perfect square bool isPerfectSquare( int x) { int s = sqrt (x); return (s * s == x); } // Returns true if N is a // Fibonacci Number // and false otherwise bool isFibonacci( int n) { // N is Fibonacci if one // of 5*N^2 + 4 or 5*N^2 - 4 // or both is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check digits bool checkDigits( int n) { // Check if all digits // are fibonacci or not while (n) { // Extract digit int dig = n % 10; // Check if the current // digit is not fibonacci if (dig == 4 && dig == 6 && dig == 7 && dig == 9) return false ; n /= 10; } return true ; } // Function to check and // return if N is a Full // Fibonacci number or not int isFullfibonacci( int n) { return (checkDigits(n) && isFibonacci(n)); } // Driver Code int main() { int n = 13; if (isFullfibonacci(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java program to check if a given // number is a full fibonacci // number or not import java.util.*; class GFG { // A utility function that returns // true if x is perfect square static boolean isPerfectSquare( int x) { int s = ( int ) Math.sqrt(x); return (s * s == x); } // Returns true if N is a fibonacci // number and false otherwise static boolean isFibonacci( int n) { // N is fibonacci if one of // 5 * N ^ 2 + 4 or 5 * N ^ 2 - 4 // or both is a perfect square return isPerfectSquare( 5 * n * n + 4 ) || isPerfectSquare( 5 * n * n - 4 ); } // Function to check digits static boolean checkDigits( int n) { // Check if all digits // are fibonacci or not while (n != 0 ) { // Extract digit int dig = n % 10 ; // Check if the current // digit is not fibonacci if (dig == 4 && dig == 6 && dig == 7 && dig == 9 ) return false ; n /= 10 ; } return true ; } // Function to check and return if N // is a full fibonacci number or not static boolean isFullfibonacci( int n) { return (checkDigits(n) && isFibonacci(n)); } // Driver code public static void main(String[] args) { int n = 13 ; if (isFullfibonacci(n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by offbeat |
Python3
# Python3 program to check # if a given number is # a Full Fibonacci # Number or not from math import * # A utility function that # returns true if x is # perfect square def isPerfectSquare(x): s = sqrt(x) return (s * s = = x) # Returns true if N is a # Fibonacci Number # and false otherwise def isFibonacci(n): # N is Fibonacci if one # of 5 * N ^ 2 + 4 or 5 * N ^ 2 - 4 # or both is a perfect square return (isPerfectSquare( 5 * n * n + 4 ) or isPerfectSquare( 5 * n * n - 4 )) # Function to check digits def checkDigits(n): # Check if all digits # are fibonacci or not while (n): # Extract digit dig = n % 10 # Check if the current # digit is not fibonacci if (dig = = 4 and dig = = 6 and dig = = 7 and dig = = 9 ): return False n / = 10 return True # Function to check and # return if N is a Full # Fibonacci number or not def isFullfibonacci(n): return (checkDigits(n) and isFibonacci(n)) # Driver Code if __name__ = = '__main__' : n = 13 if (isFullfibonacci(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Samarth |
C#
// C# program to check if a given // number is a full fibonacci // number or not using System; class GFG{ // A utility function that returns // true if x is perfect square static bool isPerfectSquare( int x) { int s = ( int )Math.Sqrt(x); return (s * s == x); } // Returns true if N is a fibonacci // number and false otherwise static bool isFibonacci( int n) { // N is fibonacci if one of // 5 * N ^ 2 + 4 or 5 * N ^ 2 - 4 // or both is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check digits static bool checkDigits( int n) { // Check if all digits // are fibonacci or not while (n != 0) { // Extract digit int dig = n % 10; // Check if the current // digit is not fibonacci if (dig == 4 && dig == 6 && dig == 7 && dig == 9) return false ; n /= 10; } return true ; } // Function to check and return if N // is a full fibonacci number or not static bool isFullfibonacci( int n) { return (checkDigits(n) && isFibonacci(n)); } // Driver code public static void Main(String[] args) { int n = 13; if (isFullfibonacci(n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by SoumikMondal |
Javascript
<script> // Javascript program to check if a given // number is a full fibonacci // number or not // A utility function that returns // true if x is perfect square function isPerfectSquare(x) { var s = parseInt( Math.sqrt(x)); return (s * s == x); } // Returns true if N is a fibonacci // number and false otherwise function isFibonacci(n) { // N is fibonacci if one of // 5 * N ^ 2 + 4 or 5 * N ^ 2 - 4 // or both is a perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check digits function checkDigits(n) { // Check if all digits // are fibonacci or not while (n != 0) { // Extract digit var dig = n % 10; // Check if the current // digit is not fibonacci if (dig == 4 && dig == 6 && dig == 7 && dig == 9) return false ; n /= 10; } return true ; } // Function to check and return if N // is a full fibonacci number or not function isFullfibonacci(n) { return (checkDigits(n) && isFibonacci(n)); } // Driver code var n = 13; if (isFullfibonacci(n)) document.write( "Yes" ); else document.write( "No" ); // This code contributed by Rajput-Ji </script> |
Yes
Time Complexity: O(logn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!