Dada una array arr[] , la tarea es encontrar el elemento que tiene el número máximo de premúltiplos presentes en el conjunto. Para cualquier índice i , pre-múltiplo es el número que es múltiplo de i y está presente antes del i -ésimo índice de la array. Además, imprima el recuento de múltiplos máximos de ese elemento en esa array.
Ejemplos:
Entrada: arr[] = {8, 1, 28, 4, 2, 6, 7}
Salida: Elemento = 2 , Recuento de premúltiplos = 3
Explicación: Para la array, arr[] = {8, 1, 28, 4 , 2, 6, 7} el número 2 tiene un número máximo
de premúltiplos, es decir, {8, 28, 4}. Por lo tanto, la cuenta es 3.
Entrada: arr[] = {8, 12, 5, 8, 17, 5, 28, 4, 3, 8}
Salida: Elemento = 4, 3, Conteo de premúltiplos = 3
para la array, a [] = {8, 12, 5, 8, 17, 5, 6, 15, 4, 3, 8} el número 4 y 3 tiene un
número máximo de premúltiplos, es decir, {8, 12, 8} y {12, 6, 15}. Por lo tanto cuenta es 3.
Enfoque: La idea es usar otra array para almacenar el conteo de múltiplos de i antes del índice. Se pueden seguir los siguientes pasos para calcular el resultado:
- Itere sobre cada elemento de la array, y para cada i válido , el recuento es igual al número de índices válidos j < i , de modo que el elemento en el índice j es divisible por el elemento en el índice i .
- Almacene el valor del conteo del elemento en el índice i de la array temp_count .
- Encuentre el elemento máximo en la array temp_count [] y almacene su valor en max .
- Iterar sobre cada elemento de la array temp_count , de modo que, si el elemento en el índice i de temp_count es igual a max , imprima el i -ésimo elemento correspondiente de la array original arr .
- Finalmente, imprima el valor máximo almacenado en max.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Element = 2, 3, 4, Count of Premultiples = 2
Complejidad del tiempo: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA