Given an array of N numbers, the task is to print all the numbers greater than 1 which divides the maximum of array elements.
Examples:
Input: a[] = {6, 6, 12, 18, 13}
Output: 2 3 6
All the numbers divide the maximum of array elements i.e., 4Input: a[] = {12, 15, 27, 20, 40}
Output: 2 3 4 5
Approach:
- Use hashing to store the count of all the factors of every array element. We can find all the factors of number in O(sqrt N).
- Traverse for all factors, and find the count of maximum array elements which are divided by numbers.
- Again re-traverse for all factors and print the factors that occur the maximum number of times.
Below is the implementation of the above approach.
C++
// C++ program to print all the numbers// that divides maximum of array elements#include <bits/stdc++.h>using namespace std;// Function that prints all the numbers// which divides maximum of array elementsvoid printNumbers(int a[], int n){ // hash to store the number of times // a factor is there unordered_map<int, int> mpp; for (int i = 0; i < n; i++) { int num = a[i]; // find all the factors for (int j = 1; j * j <= num; j++) { // if j is factor of num if (num % j == 0) { if (j != 1) mpp[j]++; if ((num / j) != j) mpp[num / j]++; } } } // find the maximum times // it can divide int maxi = 0; for (auto it : mpp) { maxi = max(it.second, maxi); } // print all the factors of // numbers which divides the // maximum array elements for (auto it : mpp) { if (it.second == maxi) cout << it.first << " "; }}// Driver Codeint main(){ int a[] = { 12, 15, 27, 20, 40 }; int n = sizeof(a) / sizeof(a[0]); printNumbers(a, n);} |
Java
// Java program to print all the numbers// that divides maximum of array elementsimport java.util.*;class GFG{ // Function that prints all the numbers// which divides maximum of array elementsstatic void printNumbers(int a[], int n){ // hash to store the number of times // a factor is there Map<Integer, Integer> mpp = new HashMap<>(); for (int i = 0; i < n; i++) { int num = a[i]; // find all the factors for (int j = 1; j * j <= num; j++) { // if j is factor of num if (num % j == 0) { if (j != 1) { if(mpp.containsKey(j)) { mpp.put(j, mpp.get(j) + 1); } else { mpp.put(j, 1); } } if ((num / j) != j) { if(mpp.containsKey(num / j)) { mpp.put(num / j, mpp.get(num / j) + 1); } else { mpp.put(num / j, 1); } } } } } // find the maximum times // it can divide int maxi = 0; for (Map.Entry<Integer, Integer> it : mpp.entrySet()) { maxi = Math.max(it.getValue(), maxi); } // print all the factors of // numbers which divides the // maximum array elements for (Map.Entry<Integer, Integer> it : mpp.entrySet()) { if (it.getValue() == maxi) System.out.print(it.getKey() + " "); }}// Driver Codepublic static void main(String[] args) { int a[] = { 12, 15, 27, 20, 40 }; int n = a.length; printNumbers(a, n);}}// This code is contributed by Princi Singh |
Python3
# Python3 program to print all the numbers# that divides maximum of array elements# Function that prints all the numbers# which divides maximum of array elementsdef printNumbers(a, n): # hash to store the number of times # a factor is there mpp = dict() for i in range(n): num = a[i] # find all the factors for j in range(1, num + 1): if j * j > num: break # if j is factor of num if (num % j == 0): if (j != 1): mpp[j]=mpp.get(j, 0) + 1 if ((num // j) != j): mpp[num // j]=mpp.get(num//j, 0) + 1 # find the maximum times # it can divide maxi = 0 for it in mpp: maxi = max(mpp[it], maxi) # print all the factors of # numbers which divides the # maximum array elements for it in mpp: if (mpp[it] == maxi): print(it,end=" ") # Driver Codea = [12, 15, 27, 20, 40 ]n = len(a)printNumbers(a, n)# This code is contributed by mohit kumar |
C#
// C# program to print all the numbers// that divides maximum of array elementsusing System;using System.Collections.Generic; class GFG{ // Function that prints all the numbers// which divides maximum of array elementsstatic void printNumbers(int []a, int n){ // hash to store the number of times // a factor is there Dictionary<int,int> mpp = new Dictionary<int,int>(); for (int i = 0; i < n; i++) { int num = a[i]; // find all the factors for (int j = 1; j * j <= num; j++) { // if j is factor of num if (num % j == 0) { if (j != 1) { if(mpp.ContainsKey(j)) { var v = mpp[j]; mpp.Remove(j); mpp.Add(j, v + 1); } else { mpp.Add(j, 1); } } if ((num / j) != j) { if(mpp.ContainsKey(num / j)) { var v = mpp[num/j]; mpp.Remove(num/j); mpp.Add(num / j, v + 1); } else { mpp.Add(num / j, 1); } } } } } // find the maximum times // it can divide int maxi = 0; foreach(KeyValuePair<int, int> it in mpp) { maxi = Math.Max(it.Value, maxi); } // print all the factors of // numbers which divides the // maximum array elements foreach(KeyValuePair<int, int> it in mpp) { if (it.Value == maxi) Console.Write(it.Key + " "); }}// Driver Codepublic static void Main(String[] args) { int []a = { 12, 15, 27, 20, 40 }; int n = a.Length; printNumbers(a, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to print all the numbers// that divides maximum of array elements// Function that prints all the numbers// which divides maximum of array elementsfunction printNumbers(a, n){ // hash to store the number of times // a factor is there var mpp = new Map(); for (var i = 0; i < n; i++) { var num = a[i]; // find all the factors for (var j = 1; j * j <= num; j++) { // if j is factor of num if (num % j == 0) { if (j != 1) { if(mpp.has(j)) mpp.set(j, mpp.get(j)+1) else mpp.set(j, 1) } if ((num / j) != j) { if(mpp.has(parseInt(num / j))) mpp.set(parseInt(num / j), mpp.get(parseInt(num / j))+1) else mpp.set(parseInt(num / j), 1) } } } } // find the maximum times // it can divide var maxi = 0; mpp.forEach((value, key) => { maxi = Math.max(value, maxi); }); // print all the factors of // numbers which divides the // maximum array elements mpp.forEach((value,key) => { if (value == maxi) { document.write(key+ " "); } });}// Driver Codevar a = [12, 15, 27, 20, 40];var n = a.length;printNumbers(a, n);</script> |
Output
2 3 5 4
Complexity Analysis:
- Time Complexity: O(N * sqrt(max(array element))), as we are using nested loops where the outer loop traverses N times and in the inner loop, the condition is j*j<=num, square rooting both the sides we will have j<=sqrt(num), so the inner loop traverses sqrt (num) times. Where N is the number of elements in the array and num is the maximum element of the array.
- Auxiliary Space: O(N * sqrt(max(array element))), as we are using extra space for the map.
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!
