Given an array arr[] of size n, The task is to find the GCD of the highest and lowest frequency element in the given array.
Examples:
Input: arr[] = {2, 2, 4, 4, 5, 5, 6, 6, 6, 6}
Output: 2
Explanation: The frequency of the elements in the above array is
freq(2) = 2,
freq(4) = 2,
freq(5) = 2,
freq(6) = 4,
The minimum frequency is 2 (of elements 2, 4, and 5). So 2 will be picked as the least among 2, 4, and 5.
The largest frequency is 4 (of element 6).
Hence GCD of 2 and 6 = gcd(2, 6) is 2.Input: arr[] = {3, 2, 2, 44, 44, 44, 44}
Output: 1
Approach: The idea is to count the frequencies of all elements and store them in a vector and then find the gcd of the highest occurring and the least occurring elements.
Algorithm:
- Define a function find_gcd that takes a vector of integers v and an integer n representing the size of the vector.
- Declare a map data structure mp that will store the frequency of each element in the vector.
- Iterate through each element in the vector v using a for loop with index i, and update the frequency of each element in the map data structure mp.
- Initialize two variables mini and maxi to the first element in the vector v.
- Iterate through each element in the map data structure mp using a range-based for loop with auto keyword.
- For each element in the map data structure mp, check if its frequency is less than the frequency of the current minimum element mini. If it is, update the value of mini to the current element. Otherwise, keep the current mini value.
- For each element in the map data structure mp, check if its frequency is greater than the frequency of the current maximum element maxi. If it is, update the value of maxi to the current element. Otherwise, keep the current maxi value.
- Use the __gcd function from the numeric library to find the GCD of the mini and maxi values, and store the result in the res variable.
- Return the res variable.
- In the main function, initialize two vectors v and v1 with integer values.
- Call the find_gcd function with v and v1, and print the returned value.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find frequency and find gcdint find_gcd(vector<int> v, int n){ map<int, int> mp; // Update the frequency for (int i = 0; i < n; i++) { mp[v[i]]++; } int mini = v[0], maxi = v[0]; for (auto it : mp) { mini = mp[mini] < it.second ? it.first : mini; } for (auto it : mp) { maxi = mp[maxi] > it.second ? it.first : maxi; } // Find gcd int res = __gcd(mini, maxi); return res;}// Driver Codeint main(){ vector<int> v = { 2, 2, 4, 4, 5, 5, 6, 6, 6, 6 }; int n = v.size(); cout << find_gcd(v, n) << endl; vector<int> v1 = { 3, 2, 2, 44, 44, 44, 44 }; cout << find_gcd(v1, v1.size()) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find frequency and find gcdstatic int find_gcd(int []v, int n){ HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Update the frequency for (int i = 0; i < n; i++) { if(mp.containsKey(v[i])){ mp.put(v[i], mp.get(v[i])+1); } else{ mp.put(v[i], 1); } } int mini = v[0], maxi = v[0]; for (Map.Entry<Integer,Integer> it : mp.entrySet()) { mini = mp.get(mini) < it.getValue() ? it.getKey() : mini; } for (Map.Entry<Integer,Integer> it : mp.entrySet()) { maxi = mp.get(maxi) > it.getValue() ? it.getKey() : maxi; } // Find gcd int res = __gcd(mini, maxi); return res;}static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } // Drive Codepublic static void main(String[] args){ int [] v = { 2, 2, 4, 4, 5, 5, 6, 6, 6, 6 }; int n = v.length; System.out.print(find_gcd(v, n) +"\n"); int [] v1 = { 3, 2, 2, 44, 44, 44, 44 }; System.out.print(find_gcd(v1, v1.length) +"\n");}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approachimport math# Function to find frequency and find gcddef find_gcd(v, n): mp = {} # Update the frequency for i in range(0, n): if v[i] in mp: mp[v[i]] += 1 else: mp[v[i]] = 1 mini = v[0] maxi = v[0] for it in mp: if mini in mp and mp[mini] < mp[it]: mini = it for it in mp: if mp[maxi] > mp[it]: maxi = it # Find gcd res = math.gcd(mini, maxi) return res# Driver Codeif __name__ == "__main__": v = [2, 2, 4, 4, 5, 5, 6, 6, 6, 6] n = len(v) print(find_gcd(v, n)) v1 = [3, 2, 2, 44, 44, 44, 44] print(find_gcd(v1, len(v1))) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Function to find frequency and find gcd static int find_gcd(int[] v, int n) { Dictionary<int, int> mp = new Dictionary<int, int>(); // Update the frequency for (int i = 0; i < n; i++) { if (mp.ContainsKey(v[i])) { mp[v[i]] += 1; } else { mp[v[i]] = 1; } } int mini = v[0], maxi = v[0]; foreach(KeyValuePair<int, int> it in mp) { mini = mp[mini] < it.Value ? it.Key : mini; } foreach(KeyValuePair<int, int> it in mp) { maxi = mp[maxi] > it.Value ? it.Key : maxi; } // Find gcd int res = __gcd(mini, maxi); return res; } // Drive Code public static void Main() { int[] v = { 2, 2, 4, 4, 5, 5, 6, 6, 6, 6 }; int n = v.Length; Console.WriteLine(find_gcd(v, n)); int[] v1 = { 3, 2, 2, 44, 44, 44, 44 }; Console.WriteLine(find_gcd(v1, v1.Length)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach function __gcd(a, 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 find frequency and find gcd function find_gcd(v, n) { let mp = new Map(); // Update the frequency for (let i = 0; i < n; i++) { if (!mp.has(v[i])) mp.set(v[i], 1); else mp.set(v[i], mp.get(v[i]) + 1) } let mini = v[0], maxi = v[0]; for (let [key, val] of mp) { mini = mp.get(mini) < val ? key : mini; } for (let [key, val] of mp) { maxi = mp.get(maxi) > val ? key : maxi; } // Find gcd let res = __gcd(mini, maxi); return res; } // Drive Code let v = [2, 2, 4, 4, 5, 5, 6, 6, 6, 6]; let n = v.length; document.write(find_gcd(v, n) + '<br>'); let v1 = [3, 2, 2, 44, 44, 44, 44]; document.write(find_gcd(v1, v1.length) + '<br>'); // This code is contributed by Potta Lokesh </script> |
Output:
2 1
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
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!
