Check if GCD of all Composite Numbers in an array divisible by K is a Fibonacci Number or not
Given array arr[] consisting of N non-negative integers, and an integer K, the task is to check if GCD of all composite numbers in the array which are divisible by K is a Fibonacci Number or not. IF found to be true, print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {13, 55, 1331, 7, 13, 11, 44, 77, 144, 89}, K = 11
Output: No
Explanation: Composite Numbers from the array which are divisible by 11 are {55, 1331, 11, 44, 77}. GCD of these elements is equal to 11, which is not a Fibonacci Number.Input: arr[] = {34, 2, 4, 8, 5, 7, 11}, K = 2
Output:Yes
Explanation: Composite Numbers from the array which are divisible by 2 are {34, 2, 4, 8}. GCD of these elements is equal to 2, which is not a Fibonacci Number.
Approach: Follow the steps below to solve the problem:
- Create a function isComposite() to check if a number is a composite number or not.
- Create another function isFibonacci() to check if a number is Fibonacci number or not.
- Initialize a vector of integers, say compositeset, and another integer variable gcd to store gcd of the composite numbers from the array which are divisible by K.
- Traverse the array arr[].
- For every element arr[i], check if it is composite and divisible by K or not. If found to be true, insert it into the vector compositeset
- Calculate GCD of all the elements in the vector compositeset and store it in the variable gcd.
- Check if gcd is a Fibonacci Number or not.
- If found to be true, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a // number is composite or not bool isComposite( int n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return false ; // Check if the number is // divisible by 2 or 3 or not if (n % 2 == 0 || n % 3 == 0) return true ; // Check if n is a multiple of // any other prime number for ( int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true ; return false ; } // Function to check if a number // is a Perfect Square or not bool isPerfectSquare( int x) { int s = sqrt (x); return (s * s == x); } // Function to check if a number // is a Fibonacci number or not bool isFibonacci( int n) { // If 5*n^2 + 4 or 5*n^2 - 4 or // both are perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check if GCD of composite // numbers from the array a[] which are // divisible by k is a Fibonacci number or not void ifgcdFibonacci( int a[], int n, int k) { vector< int > compositeset; // Traverse the array for ( int i = 0; i < n; i++) { // If array element is composite // and divisible by k if (isComposite(a[i]) && a[i] % k == 0) { compositeset.push_back(a[i]); } } int gcd = compositeset[0]; // Calculate GCD of all elements in compositeset for ( int i = 1; i < compositeset.size(); i++) { gcd = __gcd(gcd, compositeset[i]); if (gcd == 1) { break ; } } // If GCD is Fibonacci if (isFibonacci(gcd)) { cout << "Yes" ; return ; } cout << "No" ; return ; } // Driver Code int main() { int arr[] = { 34, 2, 4, 8, 5, 7, 11 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 2; ifgcdFibonacci(arr, n, k); return 0; } |
Java
// Java Program for the above approach import java.util.*; class GFG{ // Function to check if a // number is composite or not static boolean isComposite( int n) { // Corner cases if (n <= 1 ) return false ; if (n <= 3 ) return false ; // Check if the number is // divisible by 2 or 3 or not if (n % 2 == 0 || n % 3 == 0 ) return true ; // Check if n is a multiple of // any other prime number for ( int i = 5 ; i * i <= n; i = i + 6 ) if (n % i == 0 || n % (i + 2 ) == 0 ) return true ; return false ; } // Function to check if a number // is a Perfect Square or not static boolean isPerfectSquare( int x) { int s = ( int )Math.sqrt(x); return (s * s == x); } // Function to check if a number // is a Fibonacci number or not static boolean isFibonacci( int n) { // If 5*n^2 + 4 or 5*n^2 - 4 or // both are perfect square return isPerfectSquare( 5 * n * n + 4 ) || isPerfectSquare( 5 * n * n - 4 ); } // Function to check if GCD of composite // numbers from the array a[] which are // divisible by k is a Fibonacci number or not static void ifgcdFibonacci( int a[], int n, int k) { Vector<Integer> compositeset = new Vector<>(); // Traverse the array for ( int i = 0 ; i < n; i++) { // If array element is composite // and divisible by k if (isComposite(a[i]) && a[i] % k == 0 ) { compositeset.add(a[i]); } } int gcd = compositeset.get( 0 ); // Calculate GCD of all elements in compositeset for ( int i = 1 ; i < compositeset.size(); i++) { gcd = __gcd(gcd, compositeset.get(i)); if (gcd == 1 ) { break ; } } // If GCD is Fibonacci if (isFibonacci(gcd)) { System.out.print( "Yes" ); return ; } System.out.print( "No" ); return ; } // Recursive function to return gcd of a and b static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Code public static void main(String[] args) { int arr[] = { 34 , 2 , 4 , 8 , 5 , 7 , 11 }; int n = arr.length; int k = 2 ; ifgcdFibonacci(arr, n, k); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach import math # Function to check if a # number is composite or not def isComposite(n): # Corner cases if n < = 1 : return False if n < = 3 : return False # Check if the number is # divisible by 2 or 3 or not if n % 2 = = 0 or n % 3 = = 0 : return True # Check if n is a multiple of # any other prime number i = 5 while i * i < = n: if ((n % i = = 0 ) or (n % (i + 2 ) = = 0 )): return True i + = 6 return False # Function to check if a number # is a Perfect Square or not def isPerfectSquare(x): s = int (math.sqrt(x)) return (s * s = = x) # Function to check if a number # is a Fibonacci number or not def isFibonacci(n): # If 5*n^2 + 4 or 5*n^2 - 4 or # both are perfect square return (isPerfectSquare( 5 * n * n + 4 ) or isPerfectSquare( 5 * n * n - 4 )) # Function to check if GCD of composite # numbers from the array a[] which are # divisible by k is a Fibonacci number or not def ifgcdFibonacci(a, n, k): compositeset = [] # Traverse the array for i in range (n): # If array element is composite # and divisible by k if (isComposite(a[i]) and a[i] % k = = 0 ): compositeset.append(a[i]) gcd = compositeset[ 0 ] # Calculate GCD of all elements in compositeset for i in range ( 1 , len (compositeset), 1 ): gcd = math.gcd(gcd, compositeset[i]) if gcd = = 1 : break # If GCD is Fibonacci if (isFibonacci(gcd)): print ( "Yes" ) return print ( "No" ) return # Driver Code if __name__ = = "__main__" : arr = [ 34 , 2 , 4 , 8 , 5 , 7 , 11 ] n = len (arr) k = 2 ifgcdFibonacci(arr, n, k) # This code is contributed by jana_sayantan |
C#
// C# Program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if a // number is composite or not static bool isComposite( int n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return false ; // Check if the number is // divisible by 2 or 3 or not if (n % 2 == 0 || n % 3 == 0) return true ; // Check if n is a multiple of // any other prime number for ( int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true ; return false ; } // Function to check if a number // is a Perfect Square or not static bool isPerfectSquare( int x) { int s = ( int )Math.Sqrt(x); return (s * s == x); } // Function to check if a number // is a Fibonacci number or not static bool isFibonacci( int n) { // If 5*n^2 + 4 or 5*n^2 - 4 or // both are perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check if GCD of composite // numbers from the array []a which are // divisible by k is a Fibonacci number or not static void ifgcdFibonacci( int []a, int n, int k) { List< int > compositeset = new List< int >(); // Traverse the array for ( int i = 0; i < n; i++) { // If array element is composite // and divisible by k if (isComposite(a[i]) && a[i] % k == 0) { compositeset.Add(a[i]); } } int gcd = compositeset[0]; // Calculate GCD of all elements in compositeset for ( int i = 1; i < compositeset.Count; i++) { gcd = __gcd(gcd, compositeset[i]); if (gcd == 1) { break ; } } // If GCD is Fibonacci if (isFibonacci(gcd)) { Console.Write( "Yes" ); return ; } Console.Write( "No" ); return ; } // Recursive function to return gcd of a and b static int __gcd( int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Code public static void Main(String[] args) { int []arr = { 34, 2, 4, 8, 5, 7, 11 }; int n = arr.Length; int k = 2; ifgcdFibonacci(arr, n, k); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript Program for the above approach function __gcd(a, b) { if (!b) { return a; } return __gcd(b, a % b); } // Function to check if a // number is composite or not function isComposite(n) { // Corner cases if (n <= 1) return false ; if (n <= 3) return false ; // Check if the number is // divisible by 2 or 3 or not if (n % 2 == 0 || n % 3 == 0) return true ; var i; // Check if n is a multiple of // any other prime number for (i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true ; return false ; } // Function to check if a number // is a Perfect Square or not function isPerfectSquare(x) { var s = Math.sqrt(x); return (s * s == x); } // Function to check if a number // is a Fibonacci number or not function isFibonacci(n) { // If 5*n^2 + 4 or 5*n^2 - 4 or // both are perfect square return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); } // Function to check if GCD of composite // numbers from the array a[] which are // divisible by k is a Fibonacci number or not function ifgcdFibonacci(a, n, k) { var compositeset = []; var i; // Traverse the array for (i = 0; i < n; i++) { // If array element is composite // and divisible by k if (isComposite(a[i]) && a[i] % k == 0) { compositeset.push(a[i]); } } var gcd = compositeset[0]; // Calculate GCD of all elements in compositeset for (i = 1; i < compositeset.length; i++) { gcd = __gcd(gcd, compositeset[i]); if (gcd == 1) { break ; } } // If GCD is Fibonacci if (isFibonacci(gcd)) { document.write( "Yes" ); return ; } document.write( "No" ); return ; } // Driver Code var arr = [34, 2, 4, 8, 5, 7, 11]; var n = arr.length; var k = 2; ifgcdFibonacci(arr, n, k); </script> |
Yes
Time Complexity: O(N*log(N)), where N is the size of the array
Auxiliary Space: O(N)