Dada una array arr[] de tamaño N y un entero D , la tarea es igualar todos los elementos de la array incrementando o disminuyendo el número mínimo de elementos de la array en D. Si no es posible hacer que todos los elementos de la array sean iguales, imprima -1 .
Ejemplos:
Entrada: N = 4, d = 2, arr[ ] = {2, 4, 6, 8}
Salida: 4
Explicación:
Incrementar arr[0] por D(=2) modifica arr[] a { 4, 4, 6 , 8 }.
Decrementar arr[2] por D(=2) modifica arr[] a { 4, 4, 4, 8 }.
Decrementar arr[3] por D(=2) modifica arr[] a { 4, 4, 4, 6 }.
Decrementar arr[3] por D(=2) modifica arr[] a { 4, 4, 4, 4 }.Entrada: N = 4, K = 3, arr[ ] = {2, 4, 5, 6}
Salida: -1
Enfoque: la idea es usar el enfoque codicioso para resolver este problema. A continuación se muestran los pasos:
- Ordena la array dada en orden ascendente.
- Observe que solo aquellos elementos de la array se pueden igualar, cuya diferencia con el elemento indexado adyacente es completamente divisible por D , es decir (a[i + 1] – a[i]) % D == 0 .
- Si alguna de las diferencias no es divisible por D , imprima -1 ya que todos los elementos de la array no pueden hacerse iguales.
- Ahora, use un enfoque codicioso aquí. Para una operación mínima, considere el elemento medio e intente cambiar todos los demás elementos a medio . Encuentre el número de operaciones requeridas para la transformación de un número, es decir , abs(mid – a[i]) / D .
- Al final, imprima el número mínimo de operaciones requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum count of operations
// required to make all array elements equal by
// incrementing or decrementing array elements by d
void numOperation(int arr[], int N, int D)
{
// Sort the array
sort(arr, arr + N);
// Traverse the array
for (int i = 0; i < N - 1; i++) {
// If difference between two consecutive
// elements are not divisible by D
if ((arr[i + 1] - arr[i]) % D != 0) {
cout << "-1";
return;
}
}
// Store minimum count of operations required to
// make all array elements equal by incrementing
// or decrementing array elements by d
int count = 0;
// Stores middle element
// of the array
int mid = arr[N / 2];
// Traverse the array
for (int i = 0; i < N; i++) {
// Update count
count += abs(mid - arr[i]) / D;
}
cout << count;
}
// Driver Code
int main()
{
// Given N & D
int N = 4, D = 2;
// Given array arr[]
int arr[] = { 2, 4, 6, 8 };
// Function Call
numOperation(arr, N, D);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find minimum count of operations
// required to make all array elements equal by
// incrementing or decrementing array elements by d
static void numOperation(int arr[], int N, int D)
{
// Sort the array
Arrays.sort(arr);
// Traverse the array
for (int i = 0; i < N - 1; i++) {
// If difference between two consecutive
// elements are not divisible by D
if ((arr[i + 1] - arr[i]) % D != 0) {
System.out.println("-1");
return;
}
}
// Store minimum count of operations required to
// make all array elements equal by incrementing
// or decrementing array elements by d
int count = 0;
// Stores middle element
// of the array
int mid = arr[N / 2];
// Traverse the array
for (int i = 0; i < N; i++) {
// Update count
count += Math.abs(mid - arr[i]) / D;
}
System.out.println(count);
}
// Driver code
public static void main(String[] args)
{
// Given N & D
int N = 4, D = 2;
// Given array arr[]
int arr[] = { 2, 4, 6, 8 };
// Function Call
numOperation(arr, N, D);
}
}
// This code is contributed by code_hunt.
Python3
# Python 3 program for the above approach
# Function to find minimum count of operations
# required to make all array elements equal by
# incrementing or decrementing array elements by d
def numOperation(arr, N, D):
# Sort the array
arr.sort()
# Traverse the array
for i in range(N - 1):
# If difference between two consecutive
# elements are not divisible by D
if ((arr[i + 1] - arr[i]) % D != 0):
print("-1")
return
# Store minimum count of operations required to
# make all array elements equal by incrementing
# or decrementing array elements by d
count = 0
# Stores middle element
# of the array
mid = arr[N // 2]
# Traverse the array
for i in range(N):
# Update count
count += abs(mid - arr[i]) // D
print(count)
# Driver Code
if __name__ == "__main__":
# Given N & D
N = 4
D = 2
# Given array arr[]
arr = [2, 4, 6, 8]
# Function Call
numOperation(arr, N, D)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find minimum count of operations
// required to make all array elements equal by
// incrementing or decrementing array elements by d
static void numOperation(int[] arr, int N, int D)
{
// Sort the array
Array.Sort(arr);
// Traverse the array
for (int i = 0; i < N - 1; i++)
{
// If difference between two consecutive
// elements are not divisible by D
if ((arr[i + 1] - arr[i]) % D != 0)
{
Console.WriteLine("-1");
return;
}
}
// Store minimum count of operations required to
// make all array elements equal by incrementing
// or decrementing array elements by d
int count = 0;
// Stores middle element
// of the array
int mid = arr[N / 2];
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update count
count += Math.Abs(mid - arr[i]) / D;
}
Console.WriteLine(count);
}
// Driver code
static public void Main()
{
// Given N & D
int N = 4, D = 2;
// Given array arr[]
int[] arr = new int[] { 2, 4, 6, 8 };
// Function Call
numOperation(arr, N, D);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program of the above approach
// Function to find minimum count of
// operations required to make all
// array elements equal by incrementing
// or decrementing array elements by d
function numOperation(arr, N, D)
{
// Sort the array
arr.sort();
// Traverse the array
for(let i = 0; i < N - 1; i++)
{
// If difference between two consecutive
// elements are not divisible by D
if ((arr[i + 1] - arr[i]) % D != 0)
{
document.write("-1");
return;
}
}
// Store minimum count of operations
// required to make all array elements
// equal by incrementing or decrementing
// array elements by d
let count = 0;
// Stores middle element
// of the array
let mid = arr[N / 2];
// Traverse the array
for(let i = 0; i < N; i++)
{
// Update count
count += Math.abs(mid - arr[i]) / D;
}
document.write(count);
}
// Driver Code
// Given N & D
let N = 4, D = 2;
// Given array arr[]
let arr = [ 2, 4, 6, 8 ];
// Function Call
numOperation(arr, N, D);
// This code is contributed by chinmoy1997pal
</script>
Producción:
4
Complejidad de tiempo: O(N * Log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kothawade29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA