Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar el número mínimo de pares necesarios para eliminar de modo que no exista ningún par en la array cuya suma de elementos sea igual a K .
Ejemplos:
Entrada: arr[] = { 3, 1, 3, 4, 3 }, K = 6
Salida: 1
Explicación:
Eliminar el par (arr[0], arr[2]) modifica arr[] a arr[] = { 1, 4, 3 }
Como no existe ningún par en arr[] cuya suma de elementos sea igual a K(=6), la salida requerida es 1.Entrada: arr = { 1, 2, 3, 4 }, K = 5
Salida: 2
Explicación:
Eliminar el par (arr[0], arr[3]) modifica arr[] a arr[] = { 2, 3 }
Eliminar el par (arr[0], arr[1]) modifica arr[] a arr[] = { }
Dado que no existe ningún par en arr[] cuya suma de elementos sea igual a K(=5), el resultado requerido es 2.
Enfoque: El problema se puede resolver utilizando la técnica de dos puntos . Siga los pasos a continuación para resolver este problema:
- Ordene la array en orden ascendente .
- Inicialice dos variables, digamos left = 0 y right = N – 1 para almacenar el índice de los punteros izquierdo y derecho respectivamente.
- Inicialice una variable, digamos cntPairs , para almacenar la cantidad mínima de pares necesarios para eliminar, de modo que no exista ningún par en la array cuya suma sea igual a K .
- Atraviese la array y verifique las siguientes condiciones.
- Si arr[left] + arr[right] == K , entonces incremente el valor de cntPairs en 1 y actualice left += 1 y right -= 1.
- Si arr[left] + arr[right] < K , entonces actualice left += 1 .
- Si arr[left] + arr[right] < K , entonces actualice right -= 1 .
- Finalmente, imprima el valor de cntPairs .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum count of pairs
// required to be removed such that no pairs
// exist whose sum equal to K
int maxcntPairsSumKRemoved(vector<int> arr, int k)
{
// Stores maximum count of pairs required
// to be removed such that no pairs
// exist whose sum equal to K
int cntPairs = 0;
// Base Case
if (arr.size() <= 1)
return cntPairs;
// Sort the array
sort(arr.begin(), arr.end());
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = arr.size() - 1;
while (left < right)
{
// Stores sum of left
// and right pointer
int s = arr[left] + arr[right];
// If s equal to k
if (s == k)
{
// Update cntPairs
cntPairs += 1;
// Update left
left += 1;
// Update right
right -= 1;
}
// If s > k
else if (s > k)
// Update right
right -= 1;
else
// Update left
left += 1;
}
// Return the cntPairs
return cntPairs;
}
// Driver Code
int main()
{
vector<int> arr = { 1, 2, 3, 4 };
int K = 5;
// Function call
cout << (maxcntPairsSumKRemoved(arr, K));
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum count of pairs
// required to be removed such that no pairs
// exist whose sum equal to K
static int maxcntPairsSumKRemoved(int[] arr, int k)
{
// Stores maximum count of pairs required
// to be removed such that no pairs
// exist whose sum equal to K
int cntPairs = 0;
// Base Case
if (arr.length <= 1)
return cntPairs;
// Sort the array
Arrays.sort(arr);
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = arr.length - 1;
while (left < right)
{
// Stores sum of left
// and right pointer
int s = arr[left] + arr[right];
// If s equal to k
if (s == k)
{
// Update cntPairs
cntPairs += 1;
// Update left
left += 1;
// Update right
right -= 1;
}
// If s > k
else if (s > k)
// Update right
right -= 1;
else
// Update left
left += 1;
}
// Return the cntPairs
return cntPairs;
}
// Driver Code
public static void main (String[] args)
{
int[] arr = { 1, 2, 3, 4 };
int K = 5;
// Function call
System.out.println (maxcntPairsSumKRemoved(arr, K));
}
}
Python3
# Python3 program to implement # the above approach # Function to find the maximum count of pairs # required to be removed such that no pairs # exist whose sum equal to K def maxcntPairsSumKRemoved(arr, k): # Stores maximum count of pairs required # to be removed such that no pairs # exist whose sum equal to K cntPairs = 0 # Base Case if not arr or len(arr) == 1: return cntPairs # Sort the array arr.sort() # Stores index of # left pointer left = 0 # Stores index of # right pointer right = len(arr) - 1 while left < right: # Stores sum of left # and right pointer s = arr[left] + arr[right] # If s equal to k if s == k: # Update cntPairs cntPairs += 1 # Update left left += 1 # Update right right-= 1 # If s > k elif s > k: # Update right right-= 1 else: # Update left left+= 1 # Return the cntPairs return cntPairs # Driver Code if __name__ == "__main__": arr =[1, 2, 3, 4] K = 5 # Function call print(maxcntPairsSumKRemoved(arr, K))
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum count of pairs
// required to be removed such that no pairs
// exist whose sum equal to K
static int maxcntPairsSumKRemoved(int[] arr, int k)
{
// Stores maximum count of pairs required
// to be removed such that no pairs
// exist whose sum equal to K
int cntPairs = 0;
// Base Case
if (arr.Length <= 1)
return cntPairs;
// Sort the array
Array.Sort(arr);
// Stores index of
// left pointer
int left = 0;
// Stores index of
// right pointer
int right = arr.Length - 1;
while (left < right)
{
// Stores sum of left
// and right pointer
int s = arr[left] + arr[right];
// If s equal to k
if (s == k)
{
// Update cntPairs
cntPairs += 1;
// Update left
left += 1;
// Update right
right -= 1;
}
// If s > k
else if (s > k)
// Update right
right -= 1;
else
// Update left
left += 1;
}
// Return the cntPairs
return cntPairs;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 2, 3, 4 };
int K = 5;
// Function call
Console.WriteLine (maxcntPairsSumKRemoved(arr, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
//Javascript program to implement
// the above approach
// Function to find the maximum count of pairs
// required to be removed such that no pairs
// exist whose sum equal to K
function maxcntPairsSumKRemoved( arr, k)
{
// Stores maximum count of pairs required
// to be removed such that no pairs
// exist whose sum equal to K
var cntPairs = 0;
// Base Case
if (arr.length <= 1)
return cntPairs;
// Sort the array
arr.sort();
// Stores index of
// left pointer
var left = 0;
// Stores index of
// right pointer
var right = arr.length - 1;
while (left < right)
{
// Stores sum of left
// and right pointer
var s = arr[left] + arr[right];
// If s equal to k
if (s == k)
{
// Update cntPairs
cntPairs += 1;
// Update left
left += 1;
// Update right
right -= 1;
}
// If s > k
else if (s > k)
// Update right
right -= 1;
else
// Update left
left += 1;
}
// Return the cntPairs
return cntPairs;
}
var arr = [ 1,2,3,4];
var K = 5;
// Function call
document.write(maxcntPairsSumKRemoved(arr, K));
//This code is contributed by SoumikMondal
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA