Given an array arr[] of N elements, the task is to find the GCD of the elements which have prime frequencies in the array.
Note: 1 is neither prime nor composite.
Examples:
Input: arr[] = {5, 4, 6, 5, 4, 6}
Output: 1
All the elements appear 2 times which is a prime
So, gcd(5, 4, 6) = 1Input: arr[] = {4, 8, 8, 1, 4, 3, 0}
Output: 4
Brute Force Approach:
- Initialize two arrays – one to store the frequency of each element in the array and another to store the count of elements that have prime frequencies.
- Traverse the frequency array and count the number of elements with prime frequencies.
- Find the GCD of the elements that have prime frequencies by iterating over the frequency array and checking the value of the count of prime frequency elements.
- Calculate the GCD of the elements that have prime frequencies by iterating over the array again and finding the GCD of elements that have a frequency equal to the GCD found in the previous step.
- Finally, return the GCD as the output.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to check if a number is prime or notbool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true;}// Function to find the GCD of elements that have prime frequencies in the arrayint gcdPrimeFreq(int arr[], int n) { // array to store the frequency of each element in the array, initialized to 0 int freq[10001] = {0}; // count the frequency of each element in the array for (int i = 0; i < n; i++) freq[arr[i]]++; // array to store the count of elements that have prime frequencies, initialized to 0 int prime_freq[10001] = {0}; for (int i = 0; i < 10001; i++) { // count the number of elements that have prime frequencies if (isPrime(freq[i])) prime_freq[freq[i]]++; } // initialize the GCD to 1 int gcd = 1; for (int i = 0; i < 10001; i++) { // if there are more than 1 elements with a prime frequency, update the GCD to the prime frequency if (prime_freq[i] > 1) { gcd = i; break; } } for (int i = 0; i < n; i++) { // if the frequency of the element is equal to the GCD found above, update the GCD to the GCD of the current element and the current GCD if (freq[arr[i]] == gcd) gcd = __gcd(gcd, arr[i]); } // return the GCD of the elements that have prime frequencies return gcd;}int main() { int arr[] = { 5, 4, 6, 5, 4, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << gcdPrimeFreq(arr, n); return 0;} |
Java
import java.util.Arrays;class GFG { // Function to check if a number is prime or not public static boolean isPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } // gcd method returns the GCD of a and b public static int gcd(int a, int b) { // if b=0, a is the GCD if (b == 0) return a; // call the gcd() method recursively by // replacing a with b and b with // modulus(a,b) as long as b != 0 else return gcd(b, a % b); } // Function to find the GCD of elements that have prime frequencies in the array public static int gcdPrimeFreq(int arr[], int n) { // array to store the frequency of each element in the array, initialized to 0 int freq[] = new int[10001]; Arrays.fill(freq, 0); // count the frequency of each element in the array for (int i = 0; i < n; i++) freq[arr[i]]++; // array to store the count of elements that have prime frequencies, initialized to 0 int prime_freq[] = new int[10001]; Arrays.fill(prime_freq, 0); for (int i = 0; i < 10001; i++) { // count the number of elements that have prime frequencies if (isPrime(freq[i])) prime_freq[freq[i]]++; } // initialize the GCD to 1 int gcd_ = 1; for (int i = 0; i < 10001; i++) { // if there are more than 1 elements with a prime frequency, update the GCD to the prime frequency if (prime_freq[i] > 1) { gcd_ = i; break; } } for (int i = 0; i < n; i++) { // if the frequency of the element is equal to the GCD found above, update the GCD to the GCD of the current element and the current GCD if (freq[arr[i]] == gcd_) gcd_ = gcd(gcd_, arr[i]); } // return the GCD of the elements that have prime frequencies return gcd_; } public static void main(String[] args) { int arr[] = { 5, 4, 6, 5, 4, 6 }; int n = arr.length; System.out.println(gcdPrimeFreq(arr, n)); }}// This code is contributed by prasad264 |
Python3
import math# Function to check if a number is prime or notdef isPrime(n): if n <= 1: return False for i in range(2, int(math.sqrt(n))+1): if n % i == 0: return False return True# Function to find the GCD of elements # that have prime frequencies in the arraydef gcdPrimeFreq(arr, n): # array to store the frequency of each element # in the array, initialized to 0 freq = [0] * 10001 # count the frequency of each element in the array for i in range(n): freq[arr[i]] += 1 # array to store the count of elements # that have prime frequencies, initialized to 0 prime_freq = [0] * 10001 for i in range(10001): # count the number of elements that have prime frequencies if isPrime(freq[i]): prime_freq[freq[i]] += 1 # initialize the GCD to 1 gcd = 1 for i in range(10001): # if there are more than 1 elements with # a prime frequency, update the GCD to the prime frequency if prime_freq[i] > 1: gcd = i break for i in range(n): # if the frequency of the element is equal # to the GCD found above, update the GCD to # the GCD of the current element and the current GCD if freq[arr[i]] == gcd: gcd = math.gcd(gcd, arr[i]) # return the GCD of the elements that have prime frequencies return gcdarr = [5, 4, 6, 5, 4, 6]n = len(arr)print(gcdPrimeFreq(arr, n)) |
C#
using System;using System.Linq;class GFG { // Function to check if a number is prime or not public static bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } // gcd method returns the GCD of a and b public static int Gcd(int a, int b) { // if b=0, a is the GCD if (b == 0) return a; // call the gcd() method recursively by // replacing a with b and b with // modulus(a,b) as long as b != 0 else return Gcd(b, a % b); } // Function to find the GCD of elements that have prime // frequencies in the array public static int GcdPrimeFreq(int[] arr, int n) { // array to store the frequency of each element in // the array, initialized to 0 int[] freq = new int[10001]; Array.Fill(freq, 0); // count the frequency of each element in the array for (int i = 0; i < n; i++) freq[arr[i]]++; // array to store the count of elements that have // prime frequencies, initialized to 0 int[] prime_freq = new int[10001]; Array.Fill(prime_freq, 0); for (int i = 0; i < 10001; i++) { // count the number of elements that have prime // frequencies if (IsPrime(freq[i])) prime_freq[freq[i]]++; } // initialize the GCD to 1 int gcd_ = 1; for (int i = 0; i < 10001; i++) { // if there are more than 1 elements with a // prime frequency, update the GCD to the prime // frequency if (prime_freq[i] > 1) { gcd_ = i; break; } } for (int i = 0; i < n; i++) { // if the frequency of the element is equal to // the GCD found above, update the GCD to the // GCD of the current element and the current // GCD if (freq[arr[i]] == gcd_) gcd_ = Gcd(gcd_, arr[i]); } // return the GCD of the elements that have prime // frequencies return gcd_; } public static void Main(string[] args) { int[] arr = { 5, 4, 6, 5, 4, 6 }; int n = arr.Length; Console.WriteLine(GcdPrimeFreq(arr, n)); }} |
Javascript
// Function to check if a number is prime or notfunction isPrime(n) { if (n <= 1) return false; for (let i = 2; i * i <= n; i++) if (n % i == 0) return false; return true;}// Function to find the GCD of elements that have prime frequencies in the arrayfunction gcdPrimeFreq(arr, n) { // array to store the frequency of each element in the array, initialized to 0 const freq = new Array(10001).fill(0); // count the frequency of each element in the array for (let i = 0; i < n; i++) freq[arr[i]]++; // array to store the count of elements that have prime frequencies, initialized to 0 const prime_freq = new Array(10001).fill(0); for (let i = 0; i < 10001; i++) { // count the number of elements that have prime frequencies if (isPrime(freq[i])) prime_freq[freq[i]]++; } // initialize the GCD to 1 let gcd = 1; for (let i = 0; i < 10001; i++) { // if there are more than 1 elements with a prime frequency, update the GCD to the prime frequency if (prime_freq[i] > 1) { gcd = i; break; } } for (let i = 0; i < n; i++) { // if the frequency of the element is equal to the GCD found above, update the GCD to the GCD of the current element and the current GCD if (freq[arr[i]] == gcd) gcd = gcdFunction(gcd, arr[i]); } // return the GCD of the elements that have prime frequencies return gcd;}// Function to find the GCD of two numbersfunction gcdFunction(a, b) { if (a == 0) return b; return gcdFunction(b % a, a);}const arr = [5, 4, 6, 5, 4, 6];const n = arr.length;console.log(gcdPrimeFreq(arr, n)); |
Output
1
Time Complexity: O(n * sqrt(max_value))
Auxiliary Space: O(max_value), as we need to store a boolean array of size max_value to mark the prime numbers.
Efficient Approach:
- Traverse the array and store the frequencies of all the elements in a map.
- Build Sieve of Eratosthenes which will be used to test the primality of a number in O(1) time.
- Calculate the gcd of elements having prime frequency using the Sieve array calculated in the previous step.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to create Sieve to check primesvoid SieveOfEratosthenes(bool prime[], int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to return the GCD of elements// in an array having prime frequencyint gcdPrimeFreq(int arr[], int n){ bool prime[n + 1]; memset(prime, true, sizeof(prime)); SieveOfEratosthenes(prime, n + 1); int i, j; // Map is used to store // element frequencies unordered_map<int, int> m; for (i = 0; i < n; i++) m[arr[i]]++; int gcd = 0; // Traverse the map using iterators for (auto it = m.begin(); it != m.end(); it++) { // Count the number of elements // having prime frequencies if (prime[it->second]) { gcd = __gcd(gcd, it->first); } } return gcd;}// Driver codeint main(){ int arr[] = { 5, 4, 6, 5, 4, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << gcdPrimeFreq(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*; class GFG{ // Function to create Sieve to check primesstatic void SieveOfEratosthenes(boolean prime[], int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to return the GCD of elements// in an array having prime frequencystatic int gcdPrimeFreq(int arr[], int n){ boolean []prime = new boolean[n + 1]; for (int i = 0; i < n + 1; i++) prime[i] = true; SieveOfEratosthenes(prime, n + 1); int i, j; // Map is used to store // element frequencies HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (i = 0 ; i < n; i++) { if(mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } int gcd = 0; // Traverse the map using iterators for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // Count the number of elements // having prime frequencies if (prime[it.getValue()]) { gcd = __gcd(gcd, it.getKey()); } } return gcd;}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); }// Driver codestatic public void main ( String []arg){ int arr[] = { 5, 4, 6, 5, 4, 6 }; int n = arr.length; System.out.println(gcdPrimeFreq(arr, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach from math import sqrt, gcd# Function to create Sieve to check primes def SieveOfEratosthenes(prime, p_size) : # False here indicates # that it is not prime prime[0] = False; prime[1] = False; for p in range(2, int(sqrt(p_size)) + 1) : # If prime[p] is not changed, # then it is a prime if (prime[p]) : # Update all multiples of p, # set them to non-prime for i in range(2 * p, p_size, p) : prime[i] = False; # Function to return the GCD of elements # in an array having prime frequency def gcdPrimeFreq(arr, n) : prime = [True] * (n + 1); SieveOfEratosthenes(prime, n + 1); # Map is used to store # element frequencies m = dict.fromkeys(arr, 0); for i in range(n) : m[arr[i]] += 1; __gcd = 0; # Traverse the map using iterators for key,value in m.items() : # Count the number of elements # having prime frequencies if (prime[value]) : __gcd = gcd(__gcd, key); return __gcd; # Driver code if __name__ == "__main__" : arr = [ 5, 4, 6, 5, 4, 6 ]; n = len(arr); print(gcdPrimeFreq(arr, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;using System.Collections.Generic; class GFG{ // Function to create Sieve to check primesstatic void SieveOfEratosthenes(bool []prime, int p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to return the GCD of elements// in an array having prime frequencystatic int gcdPrimeFreq(int []arr, int n){ int i; bool []prime = new bool[n + 1]; for (i = 0; i < n + 1; i++) prime[i] = true; SieveOfEratosthenes(prime, n + 1); // Map is used to store // element frequencies Dictionary<int, int> mp = new Dictionary<int, int>(); for (i = 0 ; i < n; i++) { if(mp.ContainsKey(arr[i])) { var val = mp[arr[i]]; mp.Remove(arr[i]); mp.Add(arr[i], val + 1); } else { mp.Add(arr[i], 1); } } int gcd = 0; // Traverse the map using iterators foreach(KeyValuePair<int, int> it in mp) { // Count the number of elements // having prime frequencies if (prime[it.Value]) { gcd = __gcd(gcd, it.Key); } } return gcd;}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); }// Driver codestatic public void Main ( String []arg){ int []arr = { 5, 4, 6, 5, 4, 6 }; int n = arr.Length; Console.WriteLine(gcdPrimeFreq(arr, n));}}// This code is contributed by Princi Singh |
Javascript
<script>// javascript implementation of the approachfunction gcd_two_numbers(x, y) { x = Math.abs(x); y = Math.abs(y); while(y) { var t = y; y = x % y; x = t; } return x;}// Function to create Sieve to check primesfunction SieveOfEratosthenes(prime, p_size){ // False here indicates // that it is not prime prime[0] = false; prime[1] = false; for (let p = 2; p * p <= p_size; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (let i = p * 2; i <= p_size; i += p) prime[i] = false; } } return prime;}// Function to return the GCD of elements// in an array having prime frequencyfunction gcdPrimeFreq( arr, n){ let prime = []; for(let i = 0;i<n+1;i++){ prime.push(true); } prime = SieveOfEratosthenes(prime, n + 1); let i, j; // Map is used to store // element frequencies let m = new Map(); for (i = 0; i < n; i++){ if(m[arr[i]]) m[arr[i]]++; else m[arr[i]] = 1; } let gcd = 0; // Traverse the map using iterators for (var it in m) { // Count the number of elements // having prime frequencies if (prime[m[it]]) { gcd = gcd_two_numbers(gcd, it); } } return gcd;}// Driver codelet a = [ 5, 4, 6, 5, 4, 6 ];let len = a.length;document.write( gcdPrimeFreq(a, len));</script> |
Output:
1
Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n), as extra space of size n is used
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!