Minimice la adición de números impares y la resta de números pares para que todos los elementos de la array sean iguales a K

Posted on by Rudeus Greyrat

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 = 1

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *