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 squarebool isPerfectSquare(int x){ int s = sqrt(x); return (s * s == x);}// Returns true if N is a// Fibonacci Number// and false otherwisebool 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 digitsbool 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 notint isFullfibonacci(int n){ return (checkDigits(n) && isFibonacci(n));}// Driver Codeint 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 notimport java.util.*;class GFG {// A utility function that returns // true if x is perfect squarestatic boolean isPerfectSquare(int x){ int s = (int) Math.sqrt(x); return (s * s == x);}// Returns true if N is a fibonacci// number and false otherwisestatic 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 digitsstatic 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 notstatic boolean isFullfibonacci(int n){ return (checkDigits(n) && isFibonacci(n));}// Driver codepublic 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 notfrom math import *# A utility function that# returns true if x is# perfect squaredef isPerfectSquare(x): s = sqrt(x) return (s * s == x)# Returns true if N is a# Fibonacci Number# and false otherwisedef 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 digitsdef 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 notdef isFullfibonacci(n): return (checkDigits(n) and isFibonacci(n))# Driver Codeif __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 notusing System;class GFG{// A utility function that returns // true if x is perfect squarestatic bool isPerfectSquare(int x){ int s = (int)Math.Sqrt(x); return (s * s == x);}// Returns true if N is a fibonacci// number and false otherwisestatic 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 digitsstatic 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 notstatic bool isFullfibonacci(int n){ return (checkDigits(n) && isFibonacci(n));}// Driver codepublic 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> |
Output:
Yes
Time Complexity: O(logn)
Auxiliary Space: O(1)
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!
