Dada una array arr[] de tamaño N , la tarea es contar el número de operaciones necesarias para hacer que todos los elementos de la array sean iguales reemplazando el elemento de array más grande con el segundo elemento de array más grande, que es estrictamente más pequeño que el elemento de array más grande.
Ejemplos:
Entrada: arr[ ] = {1, 1, 2, 2, 3}
Salida: 4
Explicación: Se requiere un total de 4 operaciones para hacer que todos los elementos de la array sean iguales.
Operación 1: Reemplace el elemento más grande (= arr[4] = 3) con el siguiente más grande (= arr[2] = 2). La array arr[] se modifica a {1, 1, 2, 2, 2 }.
Operación 2: Reemplace el elemento más grande (= arr[2] = 2) con el siguiente más grande (= arr[0] = 1). La array arr[] se modifica a {1, 1, 1 , 2, 2}
Operación 3: Reemplace el elemento más grande (= arr[3] = 2) con el siguiente más grande (= arr[0] = 1). La array arr[] se modifica a {1, 1, 1, 1 , 2}
Operación 4: Reemplace el elemento más grande (= arr[4] = 2) con el siguiente más grande (= arr[0] = 1). La array arr[] se modifica a {1, 1, 1, 1, 1 }Entrada: arr[ ] = {1, 1, 1}
Salida: 0
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, diga value_count = 0 y operation_count = 0 .
- Ordene la array arr[] en orden ascendente .
- Recorra la array arr[] y verifique si el elemento actual es mayor que el elemento anterior. Si se determina que es cierto , aumente value_count en 1 .
- Para cada iteración, agregue value_count en operation_count .
- Finalmente, imprima el valor de operation_count .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Make all array elements
// equal by perform certain operation
#include <bits/stdc++.h>
using namespace std;
// Function to count number of operations
// required to make all array elements equal
int operation(int arr[], int n)
{
// Initialize the val_count
// and operation_count by 0.
int val_count = 0, operation_count = 0;
// Sort the array in ascending order.
sort(arr, arr + n);
for (int i = 1; i < n; i++) {
// Current element greater
// than the previous element
if (arr[i - 1] < arr[i]) {
// If yes then update the
// val_count by 1.
val_count++;
}
// Add the value_count in operation_count.
operation_count = operation_count + val_count;
}
// Return the operation_count
return operation_count;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 1, 1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << operation(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
import java.io.*;
class GFG
{
// Function to count number of operations
// required to make all array elements equal
static int operation(int arr[], int n)
{
// Initialize the val_count
// and operation_count by 0.
int val_count = 0, operation_count = 0;
// Sort the array in ascending order.
Arrays.sort(arr);
for (int i = 1; i < n; i++) {
// Current element greater
// than the previous element
if (arr[i - 1] < arr[i]) {
// If yes then update the
// val_count by 1.
val_count++;
}
// Add the value_count in operation_count.
operation_count = operation_count + val_count;
}
// Return the operation_count
return operation_count;
}
// Driver Code
public static void main (String[] args)
{
// Given Input
int arr[] = { 1, 1, 2, 2, 3 };
int n = arr.length;
// Function Call
System.out.println( operation(arr, n));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python3 program to Make all array elements # equal by perform certain operation # Function to count number of operations # required to make all array elements equal def operation(arr, n): # Initialize the val_count # and operation_count by 0. val_count = 0 operation_count = 0 # Sort the array in ascending order. arr.sort() for i in range(1, n): # Current element greater # than the previous element if arr[i-1] < arr[i]: # If yes then update the # val_count by 1. val_count += 1 # Add the value_count in operation_count. operation_count += val_count # Return the operation_count return operation_count # Driver code arr = [1, 1, 2, 2, 3] n = len(arr) print(operation(arr, n)) # This code is contributed by Parth Manchanda
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to count number of operations
// required to make all array elements equal
static int operation(int []arr, int n)
{
// Initialize the val_count
// and operation_count by 0.
int val_count = 0, operation_count = 0;
// Sort the array in ascending order.
Array.Sort(arr);
for (int i = 1; i < n; i++) {
// Current element greater
// than the previous element
if (arr[i - 1] < arr[i]) {
// If yes then update the
// val_count by 1.
val_count++;
}
// Add the value_count in operation_count.
operation_count = operation_count + val_count;
}
// Return the operation_count
return operation_count;
}
// Driver Code
public static void Main(String[] args)
{
// Given Input
int []arr = { 1, 1, 2, 2, 3 };
int n = arr.Length;
// Function Call
Console.WriteLine( operation(arr, n));
}
}
// This code is contributed by Amit Katiyar
Javascript
// Javascript program to Make all array elements
// equal by perform certain operation
// Function to count number of operations
// required to make all array elements equal
function operation(arr, n) {
// Initialize the val_count
// and operation_count by 0.
let val_count = 0,
operation_count = 0;
// Sort the array in ascending order.
arr.sort();
for (let i = 1; i < n; i++) {
// Current element greater
// than the previous element
if (arr[i - 1] < arr[i]) {
// If yes then update the
// val_count by 1.
val_count++;
}
// Add the value_count in operation_count.
operation_count = operation_count + val_count;
}
// Return the operation_count
return operation_count;
}
// Driver Code
// Given Input
let arr = [1, 1, 2, 2, 3];
let n = arr.length;
// Function Call
document.write(operation(arr, n));
// This code is contributed by gfgking.
4
Complejidad temporal: O(NLogN)
Espacio auxiliar: O(1)