Dada una array A[] de enteros cuya longitud es N , (donde N es par), la tarea es verificar si A[] se puede agrupar en N/2 pares que tengan la misma suma.
Ejemplos:
Entrada: N = 6, A[] = {4, 5, 3, 1, 2, 6}
Salida: Verdadero
Explicación: Considere los pares {1, 6}, {5, 2} y {4, 3}.
Los 3 tienen una suma = 7.
Por lo tanto, la array dada se puede dividir en N/2, es decir, 3 pares que tienen la misma suma.Entrada: N = 8, A[] = {1, 1, 1, 1, 1, 1, 2, 3}
Salida: Falso
Enfoque: La idea para resolver el problema es utilizar un enfoque de dos punteros siguiendo la siguiente observación.
Si existen N/2 pares que tienen la misma suma, entonces la suma de cada par debe ser igual a min + max , donde min es el elemento mínimo de la array y max es el elemento máximo de la array.
Siga los pasos mencionados a continuación para resolver el problema basado en la observación anterior:
- Ordenar la array dada.
- Inicialice una variable (por ejemplo , target ) igual a la suma del primer y último elemento de la array ordenada.
- Inicialice dos punteros que apunten al primer y último elemento.
- Incremente y disminuya los punteros simultáneamente y verifique si la suma de los elementos en los punteros es igual al objetivo.
- Si es así, continúe con la iteración.
- De lo contrario, devuelve falso.
- Una vez completada la iteración, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to divide the given array into
// N/2 pairs having equal sum
bool isPossible(int N, int A[])
{
// Sorting the given array
sort(A, A + N);
// Initializing target as the sum of
// minimum and maximum element
int target = A[0] + A[N - 1];
// Initializing two pointers
int i = 0, j = N - 1;
while (i < j) {
// If sum of elements at i and j
// is equal to target then,
// increment and decrement i and j
// respectively
if (A[i] + A[j] == target) {
i++;
j--;
}
// Else return false
else {
return false;
}
}
// After whole array is traversed,
// which means N/2 pairs have sum
// equal to target, hence return true
return true;
}
// Driver Code
int main()
{
int N = 6;
int A[] = { 4, 5, 3, 1, 2, 6 };
// Function call
bool answer = isPossible(N, A);
if (answer)
cout << "True";
else
cout << "False";
return 0;
}
Java
// JAVA code for the above approach.
import java.util.*;
class GFG
{
// Function to check if it is possible
// to divide the given array into
// N/2 pairs having equal sum
public static boolean isPossible(int N, int A[])
{
// Sorting the given array
Arrays.sort(A);
// Initializing target as the sum of
// minimum and maximum element
int target = A[0] + A[N - 1];
// Initializing two pointers
int i = 0, j = N - 1;
while (i < j) {
// If sum of elements at i and j
// is equal to target then,
// increment and decrement i and j
// respectively
if (A[i] + A[j] == target) {
i++;
j--;
}
// Else return false
else {
return false;
}
}
// After whole array is traversed,
// which means N/2 pairs have sum
// equal to target, hence return true
return true;
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
int A[] = { 4, 5, 3, 1, 2, 6 };
// Function call
boolean answer = isPossible(N, A);
if (answer)
System.out.print("True");
else
System.out.print("False");
}
}
// This code is contributed by Taranpreet
Python3
# Python3 code for the above approach.
# Function to check if it is possible
# to divide the given array into
# N/2 pairs having equal sum
def isPossible(N, A):
# Sorting the given array
A.sort()
# Initializing target as the sum of
# minimum and maximum element
target = A[0] + A[N - 1]
# Initializing two pointers
i = 0
j = N - 1
while (i < j):
# If sum of elements at i and j
# is equal to target then,
# increment and decrement i and j
# respectively
if (A[i] + A[j] == target):
i += 1
j -= 1
# Else return false
else:
return False
# After whole array is traversed,
# which means N/2 pairs have sum
# equal to target, hence return true
return True
# Driver Code
N = 6
A = [ 4, 5, 3, 1, 2, 6 ]
# Function call
answer = isPossible(N, A)
if (answer):
print("True")
else:
print("False")
# This code is contributed by shinjanpatra
C#
// C# code for the above approach.
using System;
public class GFG{
// Function to check if it is possible
// to divide the given array into
// N/2 pairs having equal sum
static bool isPossible(int N, int[] A){
// Sorting the given array
Array.Sort(A);
// Initializing target as the sum of
// minimum and maximum element
int target = A[0] + A[N - 1];
// Initializing two pointers
int i = 0, j = N - 1;
while (i < j) {
// If sum of elements at i and j
// is equal to target then,
// increment and decrement i and j
// respectively
if (A[i] + A[j] == target) {
i++;
j--;
}
// Else return false
else {
return false;
}
}
// After whole array is traversed,
// which means N/2 pairs have sum
// equal to target, hence return true
return true;
}
// Driver Code
static public void Main (){
int N = 6;
int[] A = { 4, 5, 3, 1, 2, 6 };
// Function call
bool answer = isPossible(N, A);
if (answer == true)
Console.Write("True");
else
Console.Write("False");
}
}
// This code is contributed by hrithikgarg03188.
Javascript
<script>
// JavaScript code for the above approach.
// Function to check if it is possible
// to divide the given array into
// N/2 pairs having equal sum
const isPossible = (N, A) => {
// Sorting the given array
A.sort();
// Initializing target as the sum of
// minimum and maximum element
let target = A[0] + A[N - 1];
// Initializing two pointers
let i = 0, j = N - 1;
while (i < j) {
// If sum of elements at i and j
// is equal to target then,
// increment and decrement i and j
// respectively
if (A[i] + A[j] == target) {
i++;
j--;
}
// Else return false
else {
return false;
}
}
// After whole array is traversed,
// which means N/2 pairs have sum
// equal to target, hence return true
return true;
}
// Driver Code
let N = 6;
let A = [4, 5, 3, 1, 2, 6];
// Function call
answer = isPossible(N, A);
if (answer)
document.write("True");
else
document.write("False");
// This code is contributed by rakeshsahni
</script>
1
Complejidad de tiempo: O (N * logN), ya que estamos utilizando la función de clasificación incorporada que costará O (N * logN).
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA