Count of Fibonacci divisors of a given number
Given a number N, the task is to find the number of divisors of N which belongs to the fibonacci series.
Examples:
Input: N = 12
Output: 3
Explanation:
1, 2 and 3 are the 3 divisors of 12 which are in the Fibonacci series.
Hence, the answer is 3.Input: N = 110
Output: 4
Explanation:
1, 2, 5 and 55 are 4 divisors of 110 which are in the Fibonacci series.
Efficient Approach:
- Create a hash table to store all the Fibonacci numbers till N, for checking in O(1) time.
- Find all divisors of N in O(?N)
- For each divisor, check if it is a Fibonacci number as well. Count the number of such divisors and print them.
Below is the implementation of the above approach:
C++
// C++ program to count number of divisors // of N which are Fibonacci numbers #include <bits/stdc++.h> using namespace std; // Function to create hash table // to check Fibonacci numbers void createHash( set< int >& hash, int maxElement) { int prev = 0, curr = 1; hash.insert(prev); hash.insert(curr); while (curr <= maxElement) { int temp = curr + prev; hash.insert(temp); prev = curr; curr = temp; } } // Function to count number of divisors // of N which are fibonacci numbers int countFibonacciDivisors( int n) { set< int > hash; createHash(hash, n); int cnt = 0; for ( int i = 1; i <= sqrt (n); i++) { if (n % i == 0) { // If divisors are equal, // check and count only one if ((n / i == i) && (hash.find(n / i) != hash.end())) cnt++; // Otherwise check and count both else { if (hash.find(n / i) != hash.end()) cnt++; if (hash.find(n / (n / i)) != hash.end()) cnt++; } } } return cnt; } // Driver code int main() { int n = 12; cout << countFibonacciDivisors(n); return 0; } |
Java
// Java program to count number of divisors // of N which are Fibonacci numbers import java.util.*; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash( HashSet<Integer> hash, int maxElement) { int prev = 0 , curr = 1 ; hash.add(prev); hash.add(curr); while (curr <= maxElement) { int temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to count number of divisors // of N which are fibonacci numbers static int countFibonacciDivisors( int n) { HashSet<Integer> hash = new HashSet<Integer>(); createHash(hash, n); int cnt = 0 ; for ( int i = 1 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { // If divisors are equal, // check and count only one if ((n / i == i) && (hash.contains(n / i))) cnt++; // Otherwise check and count both else { if (hash.contains(n / i)) cnt++; if (hash.contains(n / (n / i))) cnt++; } } } return cnt; } // Driver code public static void main(String[] args) { int n = 12 ; System.out.print(countFibonacciDivisors(n)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to count number of divisors # of N which are Fibonacci numbers from math import sqrt,ceil,floor # Function to create hash table # to check Fibonacci numbers def createHash(maxElement): prev = 0 curr = 1 d = dict () d[prev] = 1 d[curr] = 1 while (curr < = maxElement): temp = curr + prev d[temp] = 1 prev = curr curr = temp return d # Function to count number of divisors # of N which are fibonacci numbers def countFibonacciDivisors(n): hash = createHash(n) cnt = 0 for i in range ( 1 , ceil(sqrt(n))): if (n % i = = 0 ): # If divisors are equal, # check and count only one if ((n / / i = = i) and (n / / i in hash )): cnt + = 1 # Otherwise check and count both else : if (n / / i in hash ): cnt + = 1 if (n / / (n / / i) in hash ): cnt + = 1 return cnt # Driver code n = 12 print (countFibonacciDivisors(n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to count number of divisors // of N which are Fibonacci numbers using System; using System.Collections.Generic; class GFG{ // Function to create hash table // to check Fibonacci numbers static void createHash( HashSet< int > hash, int maxElement) { int prev = 0, curr = 1; hash.Add(prev); hash.Add(curr); while (curr <= maxElement) { int temp = curr + prev; hash.Add(temp); prev = curr; curr = temp; } } // Function to count number of divisors // of N which are fibonacci numbers static int countFibonacciDivisors( int n) { HashSet< int > hash = new HashSet< int >(); createHash(hash, n); int cnt = 0; for ( int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // check and count only one if ((n / i == i) && (hash.Contains(n / i))) cnt++; // Otherwise check and count both else { if (hash.Contains(n / i)) cnt++; if (hash.Contains(n / (n / i))) cnt++; } } } return cnt; } // Driver code public static void Main(String[] args) { int n = 12; Console.Write(countFibonacciDivisors(n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to count number of divisors // of N which are Fibonacci numbers // Function to create hash table // to check Fibonacci numbers function createHash( hash, maxElement) { let prev = 0, curr = 1; hash.add(prev); hash.add(curr); while (curr <= maxElement) { let temp = curr + prev; hash.add(temp); prev = curr; curr = temp; } } // Function to count number of divisors // of N which are fibonacci numbers function countFibonacciDivisors(n) { let hash = new Set(); createHash(hash, n); let cnt = 0; for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // check and count only one if ((n / i == i) && (hash.has(n / i))) cnt++; // Otherwise check and count both else { if (hash.has(n / i)) cnt++; if (hash.has(n / (n / i))) cnt++; } } } return cnt; } // Driver Code let n = 12; document.write(countFibonacciDivisors(n)); </script> |
Output:
3
Time Complexity: O(?N)
Auxiliary Space: O(N)