Given an array arr[] of integers N, the task is to find the GCD of all numbers for which it’s value is equal to its frequency in the array.
Examples;
Input: arr={2, 3, 4, 2, 3, 3} N=6
Output: 1
Explanation: Here 2 is occurring 2 times and 3 is occurring 3 times.
Hence GCD of 2, 3, is 1. So our output is 1.
Input: arr={2, 3, 4, 4, 3, 5, 4, 4, 2, 8} N=10
Output: 2
Explanation: Here 2 is occurring 2 times, 4 is occurring 4 times.
HenceGCD of 2, 4, is 2. So our output is 2.
Approach: The idea to solve the problem is as following:
Find the elements whose value is equal to its frequency. Then calculate the GCD of those number.
Follow the steps mentioned below to solve the problem:
- Find frequencies of all the numbers of the array.
- From the array find the numbers having frequency same as its value and store them.
- Calculate the GCD of those numbers.
- Return the GCD.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find GCDint findGcd(int arr[], int n){ vector<int> v; // Declaration of map unordered_map<int, int> m1; for (int i = 0; i < n; i++) { m1[arr[i]]++; } unordered_map<int, int>::iterator it; for (it = m1.begin(); it != m1.end(); ++it) { if (it->second == it->first) // Pushing superior numbers // into vector. v.push_back(it->first); } int hcf; if (v.size() == 0) return 0; else if (v.size() == 1) return v[0]; else if (v.size() == 2) { hcf = __gcd(v[0], v[1]); return hcf; } else if (v.size() > 2) { hcf = __gcd(v[0], v[1]); for (int i = 2; i < v.size(); i++) { hcf = __gcd(v[i], hcf); } return hcf; } return 1;}// Driver Codeint main(){ int N = 10; int arr[N] = { 2, 3, 4, 4, 3, 5, 4, 4, 2, 8 }; // Function call cout << findGcd(arr, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.Map.Entry;class GFG { public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find GCD public static int findGcd(int arr[], int n) { ArrayList<Integer> v = new ArrayList<Integer>(); // Declaration of map HashMap<Integer, Integer> m1 = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { if (m1.get(arr[i]) != null) m1.put(arr[i], m1.get(arr[i]) + 1); else m1.put(arr[i], 1); } Iterator<Entry<Integer, Integer> > iter = m1.entrySet().iterator(); // Iterating every set of entry in the HashMap while (iter.hasNext()) { Map.Entry<Integer, Integer> it = (Map.Entry<Integer, Integer>)iter.next(); if (it.getValue() == it.getKey()) // Pushing superior numbers // into vector. v.add(it.getKey()); } int hcf = 0; if (v.size() == 0) return 0; else if (v.size() == 1) return v.get(0); else if (v.size() == 2) { hcf = gcd(v.get(0), v.get(1)); return hcf; } else if (v.size() > 2) { hcf = gcd(v.get(0), v.get(1)); for (int i = 2; i < v.size(); i++) { hcf = gcd(v.get(i), hcf); } return hcf; } return 1; } public static void main(String[] args) { int N = 10; int arr[] = { 2, 3, 4, 4, 3, 5, 4, 4, 2, 8 }; // Function call System.out.print(findGcd(arr, N)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approachimport math# Function to find GCDdef findGcd(arr, n): v = [] # Declaration of map/dictionary m1 = dict() for i in range(n): if arr[i] in m1: m1[arr[i]] += 1 else: m1[arr[i]] = 1 for it in m1: if m1[it] == it: v.append(it) if len(v) == 0: return 0 elif len(v) == 1: return v[0] elif len(v) == 2: hcf = math.gcd(v[0], v[1]) return hcf elif len(v) > 2: hcf = math.gcd(v[0], v[1]) for i in range(2, len(v)): hcf = math.gcd(hcf, v[i]) return hcf return 1# driver codeN = 10arr = [2, 3, 4, 4, 3, 5, 4, 4, 2, 8]# function callprint(findGcd(arr, N))# This code is contributed by phasing17. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Function to calculate GCD public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find GCD public static int findGcd(int[] arr, int n) { List<int> v = new List<int>(); // Declaration of dictionary IDictionary<int, int> m1 = new Dictionary<int, int>(); // building the frequency dictionary for (int i = 0; i < n; i++) { if (m1.ContainsKey(arr[i])) m1[arr[i]] += 1; else m1[arr[i]] = 1; } // iterating over each entry in m1 // to find which keys have equivalent values foreach(KeyValuePair<int, int> entry in m1) { if (entry.Value == entry.Key) v.Add(entry.Value); } // calculating gcd int hcf = 0; if (v.Count == 0) return 0; if (v.Count == 1) return v[0]; if (v.Count == 2) { hcf = gcd(v[0], v[1]); return hcf; } if (v.Count > 2) { hcf = gcd(v[0], v[1]); for (int i = 2; i < v.Count; i++) { hcf = gcd(v[i], hcf); } return hcf; } return 1; } // Driver code public static void Main(string[] args) { int N = 10; int[] arr = { 2, 3, 4, 4, 3, 5, 4, 4, 2, 8 }; // Function call Console.WriteLine(findGcd(arr, N)); }}// this code is contributed by phasing17 |
Javascript
<script>// JavaScript code to implement the approach'use strict';// Function for calculating gcdfunction gcd(a, b){ if (b == 0) return a; return gcd(b, a % b);}// Function to find GCDfunction findGcd(arr, n){ var v = []; // Declaration of map var m1 = {}; for (var i = 0; i < n; i++) { if (m1.hasOwnProperty(arr[i])) m1[arr[i]] += 1; else m1[arr[i]] = 1; } //iterating through all the keys of m1 for (const it of Object.keys(m1)) { if (m1[it] == it) v.push(it); } if (v.length == 0) return 0; else if (v.length == 1) return v[0]; else if (v.length == 2) { var hcf = gcd(v[0], v[1]); return hcf; } else if (v.length > 2) { var hcf = math.gcd(v[0], v[1]); for (var i = 2; i < v.length; i++) hcf = math.gcd(hcf, v[i]); return hcf; } return 1;}// driver codevar N = 10;var arr = [2, 3, 4, 4, 3, 5, 4, 4, 2, 8];// function calldocument.write(findGcd(arr, N));// This code is contributed by phasing17.</script> |
Output
2
Time Complexity: time required for finding gcd of all the elements in the vector will be overall time complexity. vector at a time can have maximum number of unique elements from the array.
so
- time needed to find gcd of two elements log(max(two numbers))
- so time required to find gcd of all unique elements will be O(unique elements *log(max(two numbers)))
So time complexity will be O(total unique elements*log(max(both numbers)))
in broader way ,we can say Time Complexity should be O(total number of unique elements* Log(n)) or we can say 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!
