Dada una array , arr[] de tamaño N y un entero K , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean iguales a K realizando las siguientes operaciones cualquier cantidad de veces:
- Convierta arr[i] en arr[i] + X , donde X es un número impar .
- Convierta arr[i] en arr[i] – Y , donde Y es un número par .
Ejemplos:
Entrada: arr[] = {8, 7, 2, 1, 3}, K = 5
Salida: 8
Explicación: Para hacer que todos los elementos de la array dada sean iguales a K(= 5), se requieren las siguientes operaciones:
arr[0 ] = arr[0] + X, X = 1
arr[0] = arr[0] – Y, Y = 4
arr[1] = arr[1] – Y, Y = 2
arr[2] = arr[2 ] + X, X = 3
arr[3] = arr[3] + X, X = 3
arr[3] = arr[3] + X, X = 1
arr[4] = arr[4] + X, X = 1
array[4] = array[4] + X, X = 1Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}, K = 3
Salida: 9
Planteamiento: El problema se puede resolver usando la técnica Greedy . Las siguientes son las observaciones:
Par + Par = Par Par +
Impar = Impar
Impar + Impar = Par
Impar + Par = Impar
Siga los pasos a continuación para resolver el problema:
- Recorra la array dada y verifique las siguientes condiciones.
- Si K > arr[i] y (K – arr[i]) % 2 == 0 entonces agregue dos números impares (X) en arr[i] . Por lo tanto, se requieren 2 operaciones en total.
- Si K > arr[i] y (K – arr[i]) % 2 != 0 entonces agregue un número impar (X) en arr[i] . Por lo tanto, se requiere un total de 1 operaciones.
- Si K < arr[i] y (arr[i] – arr[i]) % 2 == 0 entonces reste un número par (Y) en arr[i] . Por lo tanto, se requiere un total de 1 operaciones.
- Si K < arr[i] y (K – arr[i]) % 2 != 0 entonces agregue un número impar (X) en arr[i] y reste un número par (Y) de arr[i] . Por lo tanto, se requieren 2 operaciones en total.
- Finalmente, imprima el número total de operaciones requeridas para hacer que todos los elementos de la array sean iguales a K .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum operations
// required to make array elements equal to K
int MinOperation(int arr[], int N, int K)
{
// Stores minimum count of operations
int cntOpe = 0;
// Traverse the given array
for (int i = 0; i < N; i++) {
// If K is greater than arr[i]
if (K > arr[i]) {
// If (K - arr[i]) is even
if ((K - arr[i]) % 2 == 0) {
// Update cntOpe
cntOpe += 2;
}
else {
// Update cntOpe
cntOpe += 1;
}
}
// If K is less than arr[i]
else if (K < arr[i]) {
// If (arr[i] - K) is even
if ((K - arr[i]) % 2 == 0) {
// Update cntOpe
cntOpe += 1;
}
else {
// Update cntOpe
cntOpe += 2;
}
}
}
return cntOpe;
}
// Driver Code
int main()
{
int arr[] = { 8, 7, 2, 1, 3 };
int K = 5;
int N = sizeof(arr) / sizeof(arr[0]);
cout << MinOperation(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to find the minimum
// operations required to make
// array elements equal to K
public static int MinOperation(int arr[],
int N, int K)
{
// Stores minimum count of
// operations
int cntOpe = 0;
// Traverse the given array
for (int i = 0; i < N; i++)
{
// If K is greater than
// arr[i]
if (K > arr[i])
{
// If (K - arr[i]) is even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 2;
}
else
{
// Update cntOpe
cntOpe += 1;
}
}
// If K is less than
// arr[i]
else if (K < arr[i])
{
// If (arr[i] - K) is
// even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 1;
}
else
{
// Update cntOpe
cntOpe += 2;
}
}
}
return cntOpe;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {8, 7, 2, 1, 3};
int K = 5;
int N = arr.length;
System.out.println(
MinOperation(arr, N, K));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement # the above approach # Function to find the minimum operations # required to make array elements equal to K def MinOperation(arr, N, K): # Stores minimum count of operations cntOpe = 0 # Traverse the given array for i in range(N): # If K is greater than arr[i] if (K > arr[i]): # If (K - arr[i]) is even if ((K - arr[i]) % 2 == 0): # Update cntOpe cntOpe += 2 else: # Update cntOpe cntOpe += 1 # If K is less than arr[i] elif (K < arr[i]): # If (arr[i] - K) is even if ((K - arr[i]) % 2 == 0): # Update cntOpe cntOpe += 1 else: # Update cntOpe cntOpe += 2 return cntOpe # Driver Code arr = [ 8, 7, 2, 1, 3 ] K = 5 N = len(arr) print(MinOperation(arr, N, K)) # This code is contributed by sanjoy_62
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the minimum
// operations required to make
// array elements equal to K
public static int MinOperation(int []arr,
int N, int K)
{
// Stores minimum count of
// operations
int cntOpe = 0;
// Traverse the given array
for(int i = 0; i < N; i++)
{
// If K is greater than
// arr[i]
if (K > arr[i])
{
// If (K - arr[i]) is even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 2;
}
else
{
// Update cntOpe
cntOpe += 1;
}
}
// If K is less than
// arr[i]
else if (K < arr[i])
{
// If (arr[i] - K) is
// even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 1;
}
else
{
// Update cntOpe
cntOpe += 2;
}
}
}
return cntOpe;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {8, 7, 2, 1, 3};
int K = 5;
int N = arr.Length;
Console.WriteLine(
MinOperation(arr, N, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the minimum
// operations required to make
// array elements equal to K
function MinOperation(arr, N, K)
{
// Stores minimum count of
// operations
let cntOpe = 0;
// Traverse the given array
for (let i = 0; i < N; i++)
{
// If K is greater than
// arr[i]
if (K > arr[i])
{
// If (K - arr[i]) is even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 2;
}
else
{
// Update cntOpe
cntOpe += 1;
}
}
// If K is less than
// arr[i]
else if (K < arr[i])
{
// If (arr[i] - K) is
// even
if ((K - arr[i]) % 2 == 0)
{
// Update cntOpe
cntOpe += 1;
}
else
{
// Update cntOpe
cntOpe += 2;
}
}
}
return cntOpe;
}
// Driver Code
let arr = [8, 7, 2, 1, 3];
let K = 5;
let N = arr.length;
document.write(
MinOperation(arr, N, K));
</script>
Producción:
8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aanchaltiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA