Given an array A[] of N non-negative integers. Find an Integer greater than 1, such that maximum array elements are divisible by it. In case of same answer print the smaller one.
Examples:
Input : A[] = { 2, 4, 5, 10, 8, 15, 16 };
Output : 2
Explanation: 2 divides [ 2, 4, 10, 8, 16] no other element divides greater than 5 numbers.’Input : A[] = { 2, 5, 10 }
Output : 2
Explanation: 2 divides [2, 10] and 5 divides [5, 10], but 2 is smaller.
Brute Force Approach:
Brute force approach to solve this problem would be to iterate over all the numbers from 2 to the maximum element in the array and check if each number is a factor of all the elements in the array. We can keep track of the number that has the maximum number of factors and return that number.
Below is the implementation of the above approach:
C++
// CPP program to find a number that// divides maximum array elements#include <bits/stdc++.h>using namespace std;// Function to find a number that// divides maximum array elementsint maxElement(int A[], int n){ int maxCount = 0, ans = 0; for (int i = 2; i <= *max_element(A, A + n); i++) { int count = 0; for (int j = 0; j < n; j++) { if (A[j] % i == 0) { count++; } } if (count > maxCount) { maxCount = count; ans = i; } } return ans;}// Driver programint main(){ int A[] = { 2, 4, 5, 10, 8, 15, 16 }; int n = sizeof(A) / sizeof(A[0]); cout << maxElement(A, n); return 0;} |
Java
import java.util.*;class Main { // Function to find a number that // divides maximum array elements static int maxElement(int[] A, int n) { int maxCount = 0, ans = 0; for (int i = 2; i <= Arrays.stream(A).max().getAsInt(); i++) { int count = 0; for (int j = 0; j < n; j++) { if (A[j] % i == 0) { count++; } } if (count > maxCount) { maxCount = count; ans = i; } } return ans; } // Driver program public static void main(String[] args) { int[] A = { 2, 4, 5, 10, 8, 15, 16 }; int n = A.length; System.out.println(maxElement(A, n)); }} |
Python3
# Python program to find a number that# divides maximum array elementsimport sys# Function to find a number that# divides maximum array elementsdef maxElement(A, n): maxCount = 0 ans = 0 for i in range(2, max(A) + 1): count = 0 for j in range(n): if A[j] % i == 0: count += 1 if count > maxCount: maxCount = count ans = i return ans# Driver programif __name__ == '__main__': A = [2, 4, 5, 10, 8, 15, 16] n = len(A) print(maxElement(A, n)) |
C#
using System;using System.Linq;public class Program{// Function to find a number that// divides maximum array elementspublic static int MaxElement(int[] A, int n){int maxCount = 0, ans = 0;for (int i = 2; i <= A.Max(); i++){int count = 0;for (int j = 0; j < n; j++){if (A[j] % i == 0){count++;}}if (count > maxCount){maxCount = count;ans = i;}}return ans;}// Driver programpublic static void Main(){ int[] A = { 2, 4, 5, 10, 8, 15, 16 }; int n = A.Length; Console.WriteLine(MaxElement(A, n));}} |
Javascript
// Function to find a number that// divides maximum array elementsfunction maxElement(A) { let maxCount = 0; let ans = 0; for (let i = 2; i <= Math.max(...A); i++) { let count = 0; for (let j = 0; j < A.length; j++) { if (A[j] % i === 0) { count++; } } if (count > maxCount) { maxCount = count; ans = i; } } return ans;}// Driver programconst A = [2, 4, 5, 10, 8, 15, 16];const n = A.length;console.log(maxElement(A)); |
Output: 2
Time Complexity: O(N^2)
Space Complexity: O(1)
Efficient Approach: We know that a number can be divisible only by elements which can be formed by their prime factors.
Thus we find the prime factors of all elements of the array and store their frequency in the hash. Finally, we return the element with maximum frequency among them.
You can use factorization-using-sieve to find prime factors in Log(n).
Below is the implementation of above approach:
C++
// CPP program to find a number that// divides maximum array elements#include <bits/stdc++.h>using namespace std;#define MAXN 100001// stores smallest prime factor for every numberint spf[MAXN];// Calculating SPF (Smallest Prime Factor) for every// number till MAXN.// Time Complexity : O(nloglogn)void sieve(){ spf[1] = 1; for (int i = 2; i < MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// A O(log n) function returning primefactorization// by dividing by smallest prime factor at every stepvector<int> getFactorization(int x){ vector<int> ret; while (x != 1) { int temp = spf[x]; ret.push_back(temp); while (x % temp == 0) x = x / temp; } return ret;}// Function to find a number that// divides maximum array elementsint maxElement(int A[], int n){ // precalculating Smallest Prime Factor sieve(); // Hash to store frequency of each divisors map<int, int> m; // Traverse the array and get spf of each element for (int i = 0; i < n; ++i) { // calling getFactorization function vector<int> p = getFactorization(A[i]); for (int i = 0; i < p.size(); i++) m[p[i]]++; } int cnt = 0, ans = 1e+7; for (auto i : m) { if (i.second >= cnt) { cnt = i.second; ans > i.first ? ans = i.first : ans = ans; } } return ans;}// Driver programint main(){ int A[] = { 2, 5, 10 }; int n = sizeof(A) / sizeof(A[0]); cout << maxElement(A, n); return 0;} |
Java
// Java program to find a number that // divides maximum array elements import java.util.*;class Solution{static final int MAXN=100001; // stores smallest prime factor for every number static int spf[]= new int[MAXN]; // Calculating SPF (Smallest Prime Factor) for every // number till MAXN. // Time Complexity : O(nloglogn) static void sieve() { spf[1] = 1; for (int i = 2; i < MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // A O(log n) function returning primefactorization // by dividing by smallest prime factor at every step static Vector<Integer> getFactorization(int x) { Vector<Integer> ret= new Vector<Integer>(); while (x != 1) { int temp = spf[x]; ret.add(temp); while (x % temp == 0) x = x / temp; } return ret; } // Function to find a number that // divides maximum array elements static int maxElement(int A[], int n) { // precalculating Smallest Prime Factor sieve(); // Hash to store frequency of each divisors Map<Integer, Integer> m= new HashMap<Integer, Integer>(); // Traverse the array and get spf of each element for (int j = 0; j < n; ++j) { // calling getFactorization function Vector<Integer> p = getFactorization(A[j]); for (int i = 0; i < p.size(); i++) m.put(p.get(i),m.get(p.get(i))==null?0:m.get(p.get(i))+1); } int cnt = 0, ans = 10000000; // Returns Set view Set< Map.Entry< Integer,Integer> > st = m.entrySet(); for (Map.Entry< Integer,Integer> me:st) { if (me.getValue() >= cnt) { cnt = me.getValue(); if(ans > me.getKey()) ans = me.getKey() ; else ans = ans; } } return ans; } // Driver program public static void main(String args[]){ int A[] = { 2, 5, 10 }; int n =A.length; System.out.print(maxElement(A, n)); } }//contributed by Arnab Kundu |
Python3
# Python3 program to find a number that # divides maximum array elementsimport math as mtMAXN = 100001# stores smallest prime factor for # every numberspf = [0 for i in range(MAXN)]# Calculating SPF (Smallest Prime Factor) # for every number till MAXN.# Time Complexity : O(nloglogn)def sieve(): spf[1] = 1 for i in range(2, MAXN): # marking smallest prime factor for # every number to be itself. spf[i] = i # separately marking spf for every # even number as 2 for i in range(4, MAXN, 2): spf[i] = 2 for i in range(3, mt.ceil(mt.sqrt(MAXN + 1))): # checking if i is prime if (spf[i] == i): # marking SPF for all numbers divisible by i for j in range(2 * i, MAXN, i): # marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i # A O(log n) function returning primefactorization# by dividing by smallest prime factor at every stepdef getFactorization (x): ret = list() while (x != 1): temp = spf[x] ret.append(temp) while (x % temp == 0): x = x //temp return ret# Function to find a number that# divides maximum array elementsdef maxElement (A, n): # precalculating Smallest Prime Factor sieve() # Hash to store frequency of each divisors m = dict() # Traverse the array and get spf of each element for i in range(n): # calling getFactorization function p = getFactorization(A[i]) for i in range(len(p)): if p[i] in m.keys(): m[p[i]] += 1 else: m[p[i]] = 1 cnt = 0 ans = 10**9+7 for i in m: if (m[i] >= cnt): cnt = m[i] if ans > i: ans = i else: ans = ans return ans# Driver CodeA = [2, 5, 10 ]n = len(A)print(maxElement(A, n))# This code is contributed by Mohit kumar 29 |
C#
// C# program to find a number that // divides maximum array elements using System;using System.Collections.Generic;class Solution{ static readonly int MAXN = 100001; // stores smallest prime factor for every number static int []spf = new int[MAXN]; // Calculating SPF (Smallest Prime Factor) for every // number till MAXN. // Time Complexity : O(nloglogn) static void sieve() { spf[1] = 1; for (int i = 2; i < MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (int i = 4; i < MAXN; i += 2) spf[i] = 2; for (int i = 3; i * i < MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (int j = i * i; j < MAXN; j += i) // marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // A O(log n) function returning primefactorization // by dividing by smallest prime factor at every step static List<int> getFactorization(int x) { List<int> ret= new List<int>(); while (x != 1) { int temp = spf[x]; ret.Add(temp); while (x % temp == 0) x = x / temp; } return ret; } // Function to find a number that // divides maximum array elements static int maxElement(int []A, int n) { // precalculating Smallest Prime Factor sieve(); // Hash to store frequency of each divisors Dictionary<int, int> m= new Dictionary<int, int>(); // Traverse the array and get spf of each element for (int j = 0; j < n; ++j) { // calling getFactorization function List<int> p = getFactorization(A[j]); for (int i = 0; i < p.Count; i++) if(m.ContainsKey(p[i])) m[p[i]] = m[p[i]] + 1; else m.Add(p[i], 1); } int cnt = 0, ans = 10000000; // Returns Set view foreach(KeyValuePair<int, int> me in m) { if (me.Value >= cnt) { cnt = me.Value; if(ans > me.Key) ans = me.Key ; else ans = ans; } } return ans; } // Driver program public static void Main(String []args){ int []A = { 2, 5, 10 }; int n =A.Length; Console.Write(maxElement(A, n)); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to find a number that // divides maximum array elements let MAXN=100001; // stores smallest prime factor for every number let spf= new Array(MAXN); for(let i=0;i<MAXN;i++){ spf[i]=0;}// Calculating SPF (Smallest Prime Factor) for every // number till MAXN. // Time Complexity : O(nloglogn) function sieve() { spf[1] = 1; for (let i = 2; i < MAXN; i++) // marking smallest prime factor for every // number to be itself. spf[i] = i; // separately marking spf for every even // number as 2 for (let i = 4; i < MAXN; i += 2) spf[i] = 2; for (let i = 3; i * i < MAXN; i++) { // checking if i is prime if (spf[i] == i) { // marking SPF for all numbers divisible by i for (let j = i * i; j < MAXN; j += i) // marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } }// A O(log n) function returning primefactorization // by dividing by smallest prime factor at every step function getFactorization(x){ let ret= []; while (x != 1) { let temp = spf[x]; ret.push(temp); while (x % temp == 0) x = Math.floor(x / temp); } return ret; }// Function to find a number that // divides maximum array elements function maxElement(A,n){ // precalculating Smallest Prime Factor sieve(); // Hash to store frequency of each divisors let m= new Map(); // Traverse the array and get spf of each element for (let j = 0; j < n; ++j) { // calling getFactorization function let p = getFactorization(A[j]); for (let i = 0; i < p.length; i++) m.set(p[i],m.get(p[i])==null?0:m.get(p[i])+1); } let cnt = 0, ans = 10000000; // Returns Set view for (let [key, value] of m.entries()) { if (value >= cnt) { cnt = value; if(ans > key) ans = key ; else ans = ans; } } return ans; }// Driver program let A=[ 2, 5, 10];let n =A.length; document.write(maxElement(A, n)); // This code is contributed by patel2127</script> |
Output
2
Time Complexity: O(N*log(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!
