Find GCD of all Array elements except the multiples of K
Given an array arr[] of N integers and an integer K, the task is to find the GCD of all the array elements except the ones which are divisible by K.
Examples:
Input: arr[] = {2, 4, 6, 8, 10}, N = 5, K = 10
Output: 2
Explanation: The multiple of K is 10.
Remaining elements are 2, 4, 6 and 8 the gcd of which are 2.Input: arr[] ={45, 15, 90, 20, 10}, N = 5, K = 15
Output: 10
Approach: The basic approach for this problem is to find the multiples of K first and then find the GCD of the remaining elements.
Follow the below steps to solve this problem:
- Iterate through all elements of an array
- Store all the elements of an array that are not divisible by K.
- Then for remaining elements, find the GCD of all the numbers.
- Return the GCD value.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to print GCD int findPrime( int arr[], int n, int k) { int i, hcf; int c = 0; // Vector used to store all the elements // which are not divisible by k vector< int > v; for (i = 0; i < n; i++) { if (arr[i] % k == 0) continue ; else v.push_back(arr[i]); } if (v.size() == 0) { cout << "NO" ; } else if (v.size() == 1) { hcf = v[0]; } else { // Finding the gcd using built in // function __gcd(value1,value2); hcf = __gcd(v[0], v[1]); for (i = 2; i < v.size(); i++) { hcf = __gcd(arr[i], hcf); } } return hcf; } // Driver Code int main() { int N = 5; int K = 10; int arr[] = { 2, 4, 6, 8, 10 }; // Function call cout << findPrime(arr, N, K); return 0; } |
C
// C code to implement the approach #include <stdio.h> #include <math.h> int gcd( int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return gcd(a-b, b); return gcd(a, b-a); } // Function to print GCD int findPrime( int arr[], int n, int k) { int i, hcf; int c = 0; // array used to store all the elements // which are not divisible by k int v[100000]; int index=0; for (i = 0; i < n; i++) { if (arr[i] % k == 0) continue ; else { v[index]=arr[i]; index++; } } if (index == 0) { printf ( "NO" ); } else if (index == 1) { hcf = v[0]; } else { // Finding the gcd using // gcd function declared above hcf = gcd(v[0], v[1]); for (i = 2; i < index+1; i++) { hcf = gcd(arr[i], hcf); } } return hcf; } // Driver Code void main() { int N = 5; int K = 10; int arr[5] = { 2, 4, 6, 8, 10 }; // Function call int ans = findPrime(arr, N, K); printf ( "%d" ,ans); } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to calculate GCD static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to print GCD static int findPrime( int arr[], int n, int k) { int i, hcf = 0 ; int c = 0 ; // Vector used to store all the elements // which are not divisible by k Vector<Integer> v = new Vector<Integer>(); for (i = 0 ; i < n; i++) { if (arr[i] % k == 0 ) continue ; else v.add(arr[i]); } if (v.size() == 0 ) { System.out.println( "NO" ); } else if (v.size() == 1 ) { hcf = v.get( 0 ); } else { // Finding the gcd using built in // function __gcd(value1,value2); hcf = gcd(v.get( 0 ), v.get( 1 )); for (i = 2 ; i < v.size(); i++) { hcf = gcd(arr[i], hcf); } } return hcf; } // Driver Code public static void main (String[] args) { int N = 5 ; int K = 10 ; int arr[] = { 2 , 4 , 6 , 8 , 10 }; // Function call System.out.println(findPrime(arr, N, K)); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code to implement the approach # Function for GCD def __gcd(a, b): if (b = = 0 ): return a return __gcd(b, a % b) # Function to print GCD def findPrime(arr, n, k): c = 0 # Vector used to store all the elements # which are not divisible by k v = [] for i in range (n): if (arr[i] % k = = 0 ): continue else : v.append(arr[i]) if ( len (v) = = 0 ): print ( "NO" ) elif ( len (v) = = 1 ): hcf = v[ 0 ] else : # Finding the gcd using built in # function __gcd(value1,value2); hcf = __gcd(v[ 0 ], v[ 1 ]) for i in range ( 2 , len (v)): hcf = __gcd(arr[i], hcf) return hcf # Driver Code N = 5 K = 10 arr = [ 2 , 4 , 6 , 8 , 10 ] # Function call print (findPrime(arr, N, K)) # This code is contributed by shinjanpatra |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to calculate GCD static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to print GCD static int findPrime( int [] arr, int n, int k) { int i; int hcf = 0; // Vector used to store all the elements // which are not divisible by k List< int > v = new List< int >(); for (i = 0; i < n; i++) { if (arr[i] % k == 0) continue ; else v.Add(arr[i]); } if (v.Count == 0) { Console.WriteLine( "NO" ); } else if (v.Count == 1) { hcf = v[0]; } else { // Finding the gcd using built in // function __gcd(value1,value2); hcf = gcd(v[0], v[1]); for (i = 2; i < v.Count; i++) { hcf = gcd(arr[i], hcf); } } return hcf; } public static void Main( string [] args) { int N = 5; int K = 10; int [] arr = { 2, 4, 6, 8, 10 }; // Function call Console.WriteLine(findPrime(arr, N, K)); } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript code to implement the approach // Functor for GCD const __gcd = (a, b) => { if (b == 0) return a; return __gcd(b, a % b); } // Function to print GCD const findPrime = (arr, n, k) => { let i, hcf; let c = 0; // Vector used to store all the elements // which are not divisible by k let v = []; for (i = 0; i < n; i++) { if (arr[i] % k == 0) continue ; else v.push(arr[i]); } if (v.length == 0) { document.write( "NO" ); } else if (v.length == 1) { hcf = v[0]; } else { // Finding the gcd using built in // function __gcd(value1,value2); hcf = __gcd(v[0], v[1]); for (i = 2; i < v.length; i++) { hcf = __gcd(arr[i], hcf); } } return hcf; } // Driver Code let N = 5; let K = 10; let arr = [2, 4, 6, 8, 10]; // Function call document.write(findPrime(arr, N, K)); // This code is contributed by rakeshsahni </script> |
Output
2
Time Complexity: O(N * log M), where M is the maximum element of the array
Auxiliary Space: O(N)