Dada una array de N enteros, la tarea es encontrar el número de operaciones necesarias para hacer que todos los elementos de la array sean iguales. En una operación podemos distribuir pesos iguales desde el elemento máximo al resto de los elementos de la array. Si no es posible igualar los elementos de la array después de realizar las operaciones anteriores, imprima -1.
Ejemplos :
Entrada : arr = [1, 6, 1, 1, 1];
Salida : 4
Explicación : dado que arr se convierte en [2, 2, 2, 2, 2] después de la distribución desde el elemento máximo.
Entrada : arr = [2, 2, 3];
Salida : -1
Explicación : aquí arr se convierte en [3, 3, 1] después de la distribución.
Algoritmo :
- Declare una variable temporal para almacenar el número de veces que se realiza la operación.
- Encuentre el elemento máximo de la array dada y almacene su valor de índice.
- Comprueba si todos los elementos son iguales al elemento máximo después de n restas.
- Nuevamente verifique que cada elemento sea igual a otros elementos y devuelva n.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
//of operations required to make
//all array elements Equal
#include<bits/stdc++.h>
using namespace std;
//Function to find maximum
//element of the given array
int find_n(int a[],int n)
{
int j = 0, k = 0, s = 0;
int x = *max_element(a, a + n);
int y = *min_element(a, a + n);
for (int i = 0; i < n; i++)
{
if (a[i] == x)
{
s = i;
break;
}
}
for (int i =0;i<n;i++)
{
if (a[i] != x && a[i] <= y && a[i] != 0)
{
a[j] += 1;
a[s] -= 1;
x -= 1;
k += 1;
j += 1;
}
else if (a[i] != 0)
{
j += 1;
}
}
for (int i = 0; i < n; i++)
{
if (a[i] != x)
{
k = -1;
break;
}
}
return k;
}
// Driver Code
int main()
{
int a[] = {1, 6, 1, 1, 1};
int n = sizeof(a)/sizeof(a[0]);
cout << (find_n(a, n));
return 0;
}
// This code contributed by princiraj1992
Java
// Java program to find the number
//of operations required to make
//all array elements Equal
import java.util.Arrays;
class GFG {
//Function to find maximum
//element of the given array
static int find_n(int[] a) {
int j = 0, k = 0, s = 0;
int x = Arrays.stream(a).max().getAsInt();
int y = Arrays.stream(a).min().getAsInt();
for (int i : a) {
if (a[i] == x) {
s = i;
break;
}
}
for (int i : a) {
if (i != x && i <= y && i != 0) {
a[j] += 1;
a[s] -= 1;
x -= 1;
k += 1;
j += 1;
} else if (i != 0) {
j += 1;
}
}
for (int i : a) {
if (a[i] != x) {
k = -1;
break;
}
}
return k;
}
//Driver Code
public static void main(String[] args) {
int[] a = {1, 6, 1, 1, 1};
System.out.println(find_n(a));
}
}
Python3
# Python program to find the number # of operations required to make # all array elements Equal # Function to find maximum # element of the given array def find_n(a): j, k = 0, 0 x = max(a) for i in range(len(a)): if(a[i] == x): s = i break for i in a: if(i != x and i <= min(a) and i !='\0'): a[j] += 1 a[s] -= 1 x -= 1 k += 1 j += 1 elif(i != '\0'): j += 1 for i in range(len(a)): if(a[i] != x): k = -1 break return k # Driver Code a = [1, 6, 1, 1, 1] print (find_n(a))
C#
// C# program to find the number
// of operations required to make
// all array elements Equal
using System;
using System.Linq;
class GFG
{
// Function to find maximum
// element of the given array
static int find_n(int []a)
{
int j = 0, k = 0, s = 0;
int x = a.Max();
int y = a.Min();
foreach(int i in a)
{
if (a[i] == x)
{
s = i;
break;
}
}
foreach (int i in a)
{
if (i != x && i <= y && i != 0)
{
a[j] += 1;
a[s] -= 1;
x -= 1;
k += 1;
j += 1;
}
else if (i != 0)
{
j += 1;
}
}
foreach (int i in a)
{
if (a[i] != x)
{
k = -1;
break;
}
}
return k;
}
// Driver Code
public static void Main()
{
int[] a = {1, 6, 1, 1, 1};
Console.Write(find_n(a));
}
}
// This code contributed by 29AjayKumar
PHP
<?php
// PHP program to find the number of
// operations required to make all
// array elements Equal
// Function to find maximum element of
// the given array
function find_n(&$a)
{
$j = 0;
$k = 0;
$x = max($a);
for ($i = 0; $i < sizeof($a); $i++)
{
if($a[$i] == $x)
{
$s = $i;
break;
}
}
for($i = 0; $i < sizeof($a); $i++)
{
if($a[$i] != $x and $a[$i] <= min($a) and
$a[$i] !=0)
{
$a[$j] += 1;
$a[$s] -= 1;
$x -= 1;
$k += 1;
$j += 1;
}
else if($a[$i] != 0)
$j += 1;
}
for($i = 0; $i < sizeof($a); $i++)
{
if($a[$i] != $x)
{
$k = -1;
break;
}
}
return $k;
}
// Driver Code
$a = array(1, 6, 1, 1, 1);
echo(find_n($a));
// This code is contributed by
// Shivi_Aggarwal
?>
Javascript
<script>
// javascript program to find the number
//of operations required to make
//all array elements Equal
//Function to find maximum
//element of the given array
function find_n(a) {
var j = 0, k = 0, s = 0;
var x = Math.max.apply(Math, a);
var y = Math.min.apply(Math, a);
for (var i = 0; i < n; i++)
{
if (a[i] == x)
{
s = i;
break;
}
}
for (var i =0;i<n;i++)
{
if (a[i] != x && a[i] <= y && a[i] != 0)
{
a[j] += 1;
a[s] -= 1;
x -= 1;
k += 1;
j += 1;
}
else if (a[i] != 0)
{
j += 1;
}
}
for (var i = 0; i < n; i++)
{
if (a[i] != x)
{
k = -1;
break;
}
}
return k;
}
//Driver Code
var a = [1, 6, 1, 1, 1];
var n = a.length;
document.write(find_n(a,n));
// This code is contributed by 29AjayKumar
</script>
Producción:
4
Complejidad de tiempo : O(n), donde n representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por AFZAL ANSARI y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA