Найдите элемент, имеющий максимальное количество предварительных чисел в массиве
Учитывая массив arr [] , задача состоит в том, чтобы найти элемент, который имеет максимальное количество предварительных кратных чисел, присутствующих в наборе. Для любого индекса i предварительное кратное - это число, кратное i и стоящее перед i- м индексом массива. Кроме того, выведите количество максимальных кратных этому элементу в этом массиве.
Примеры:
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.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея состоит в том, чтобы использовать другой массив для хранения количества кратных i перед индексом. Для вычисления результата можно выполнить следующие шаги:
- Выполните итерацию по каждому элементу массива, и для каждого действительного i счетчик равен количеству действительных индексов j <i , так что элемент с индексом j делится на элемент с индексом i .
- Сохраните значение счетчика элемента в индексе i массива temp_count.
- Найдите максимальный элемент в массиве temp_count [] и сохраните его значение в max .
- Выполните итерацию по каждому элементу массива temp_count, так что, если элемент с индексом i в temp_count равен max, выведите соответствующий i- й элемент исходного массива arr .
- Наконец, выведите максимальное значение, хранящееся в max.
Ниже представлена реализация описанного выше подхода:
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 << "
" ;} // Driver functionint main(){ int arr[] = { 8, 6, 2, 5, 8, 6, 3, 4 }; int n = sizeof (arr) / sizeof (arr[0]); printMaxMultiple(arr, n); return 0;} |
Ява
// 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 Codepublic 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 prall 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 |
Элемент = 2, 3, 4, количество предварительных кратных = 2
Сложность времени: O (N 2 )
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.