Find the element having maximum premutiples in the array
Given an array arr[], the task is to find the element which has the maximum number of pre-multiples present in the set. For any index i, pre-multiple is the number that is multiple of i and is present before the ith index of the array. Also, print the count of maximum multiples of that element in that array.
Examples:
Input: arr[] = {8, 1, 28, 4, 2, 6, 7}
Output: Element = 2 , Count of Premultiples = 3
Explanation: For the array, arr[] = {8, 1, 28, 4, 2, 6, 7} the number 2 has maximum
number of premultiples i.e. {8, 28, 4}. Therefore count is 3.Input: arr[] = {8, 12, 5, 8, 17, 5, 28, 4, 3, 8}
Output: Element = 4, 3, Count of Premultiples = 3
for the array, a[] = {8, 12, 5, 8, 17, 5, 6, 15, 4, 3, 8} the number 4 and 3 has maximum
number of premultiples i.e. {8, 12, 8} and {12, 6, 15}. Therefore count is 3.
Approach: The idea is to use another array to store the count of multiples of i before the index. The following steps can be followed to compute the result:
- Iterate over every element of the array, and for each valid i, the count is equal to the number of valid indexes j < i, such that, the element at index j is divisible by the element at index i.
- Store the value of the count of the element at index i of temp_count array.
- Find the maximum element in array temp_count[] and store its value in max.
- Iterate over every element of array temp_count, such that, if the element at index i of temp_count is equal to max then print the corresponding ith element of original array arr.
- Finally, print the maximum value stored in max.
Below is the implementation of the above approach:
C++
// C++ program to find the element which has maximum // number of premultiples and also print its count. #include <bits/stdc++.h> using namespace std; #define MAX 1000 // Function to find the elements having // maximum number of premultiples. void printMaxMultiple( int arr[], int n) { int i, j, count, max; // Initialize of temp_count array with zero int temp_count[n] = { 0 }; for (i = 1; i < n; i++) { // Initialize count with zero for // every ith element of arr[] count = 0; // Loop to calculate the count of multiples // for every ith element of arr[] before it for (j = 0; j < i; j++) { // Condition to check whether the element // at a[i] divides element at a[j] if (arr[j] % arr[i] == 0) count = count + 1; } temp_count[i] = count; } cout<< "Element = " ; // To get the maximum value in temp_count[] max = *max_element(temp_count, temp_count + n); // To print all the elements having maximum // number of multiples before them. for (i = 0; i < n; i++) { if (temp_count[i] == max) cout << arr[i] << ", " ; } cout << "Count of Premultiples = " ; // To print the count of maximum number // of multiples cout << max << "\n" ; } // Driver function int main() { int arr[] = { 8, 6, 2, 5, 8, 6, 3, 4 }; int n = sizeof (arr) / sizeof (arr[0]); printMaxMultiple(arr, n); return 0; } |
Java
// Java program to find the element which has maximum // number of premultiples and also print its count. import java.io.*; import java.util.Arrays; class GFG{ public static int MAX = 1000 ; // Function to find the elements having // maximum number of premultiples. public static void printMaxMultiple( int [] arr, int n) { int i, j, count, max; // Initialize of temp_count array with zero int [] temp_count = new int [n]; for (i = 0 ; i < temp_count.length; i++) { temp_count[i] = 0 ; } for (i = 1 ; i < n; i++) { // Initialize count with zero for // every ith element of arr[] count = 0 ; // Loop to calculate the count of multiples // for every ith element of arr[] before it for (j = 0 ; j < i; j++) { // Condition to check whether the element // at a[i] divides element at a[j] if (arr[j] % arr[i] == 0 ) count = count + 1 ; } temp_count[i] = count; } System.out.print( "Element = " ); // To get the maximum value in temp_count[] max = Arrays.stream(temp_count).max().getAsInt(); // To print all the elements having maximum // number of multiples before them. for (i = 0 ; i < n; i++) { if (temp_count[i] == max) System.out.print(arr[i] + ", " ); } System.out.print( "Count of Premultiples = " ); // To print the count of maximum number // of multiples System.out.println(max); } // Driver Code public static void main(String[] args) { int [] arr = { 8 , 6 , 2 , 5 , 8 , 6 , 3 , 4 }; int n = arr.length; printMaxMultiple(arr, n); } } // This code is contributed by shubhamsingh10 |
Python3
# Python3 program to find the element which has maximum # number of premultiples and also print count. MAX = 1000 # Function to find the elements having # maximum number of premultiples. def printMaxMultiple(arr, n): # Initialize of temp_count array with zero temp_count = [ 0 ] * n for i in range ( 1 , n): # Initialize count with zero for # every ith element of arr[] count = 0 # Loop to calculate the count of multiples # for every ith element of arr[] before it for j in range (i): # Condition to check whether the element # at a[i] divides element at a[j] if (arr[j] % arr[i] = = 0 ): count = count + 1 temp_count[i] = count print ( "Element = " ,end = "") # To get the maximum value in temp_count[] maxx = max (temp_count) # To print all the elements having maximum # number of multiples before them. for i in range (n): if (temp_count[i] = = maxx): print (arr[i],end = ", " ,sep = "") print ( "Count of Premultiples = " ,end = "") # To print the count of the maximum number # of multiples print (maxx) # Driver function arr = [ 8 , 6 , 2 , 5 , 8 , 6 , 3 , 4 ] n = len (arr) printMaxMultiple(arr, n) # This code is contributed by shubhamsingh10 |
C#
// C# program to find the element which has maximum // number of premultiples and also print its count. using System; using System.Linq; class GFG { // Function to find the elements having // maximum number of premultiples. public static void printMaxMultiple( int [] arr, int n) { int i, j, count, max; // Initialize of temp_count array with zero int [] temp_count = new int [n]; for (i = 0; i < temp_count.Length; i++) temp_count[i] = 0; for (i = 1; i < n; i++) { // Initialize count with zero for // every ith element of arr[] count = 0; // Loop to calculate the count of multiples // for every ith element of arr[] before it for (j = 0; j < i; j++) { // Condition to check whether the element // at a[i] divides element at a[j] if (arr[j] % arr[i] == 0) count = count + 1; } temp_count[i] = count; } Console.Write( "Element = " ); // To get the maximum value in temp_count[] max = temp_count.Max();; // To print all the elements having maximum // number of multiples before them. for (i = 0; i < n; i++) { if (temp_count[i] == max) Console.Write(arr[i]+ ", " ); } Console.Write( "Count of Premultiples = " ); // To print the count of maximum // number of multiples Console.WriteLine(max); } // Driver function public static void Main() { int [] arr = { 8, 6, 2, 5, 8, 6, 3, 4 }; int n = arr.Length; printMaxMultiple(arr, n); } } // This code is contributed by Shubhamsingh10 |
Javascript
<script> // JavaScript program to find // the element which has maximum // number of premultiples and also print its count. // Function to find the elements having // maximum number of premultiples. function printMaxMultiple(arr,n) { let i, j, count, max; // Initialize of temp_count array with zero let temp_count = new Array(n); temp_count.fill(0); for (i = 1; i < n; i++) { // Initialize count with zero for // every ith element of arr[] count = 0; // Loop to calculate the count of multiples // for every ith element of arr[] before it for (j = 0; j < i; j++) { // Condition to check whether the element // at a[i] divides element at a[j] if (arr[j] % arr[i] == 0) count = count + 1; } temp_count[i] = count; } document.write( "Element = " ); // To get the maximum value in temp_count[] max = Number.MIN_VALUE; for (i = 0; i < n; i++) { max = Math.max(max, temp_count[i]); } // To print all the elements having maximum // number of multiples before them. for (i = 0; i < n; i++) { if (temp_count[i] == max) document.write(arr[i] + ", " ); } document.write( "Count of Premultiples = " ); // To print the count of maximum number // of multiples document.write(max + "</br>" ); } let arr = [ 8, 6, 2, 5, 8, 6, 3, 4 ]; let n = arr.length; printMaxMultiple(arr, n); </script> |
Element = 2, 3, 4, Count of Premultiples = 2
Time Complexity: O(N2)
Auxiliary Space: O(N), where N is the size of the given array.
Contact Us