Dada una array arr[] que consta de N enteros y un entero X , la tarea es encontrar dos elementos de la array arr[] que tengan una suma X . Si no existen tales números, imprima «-1» .
Ejemplos:
Entrada: arr[] = {0, -1, 2, -3, 1}, X = -2
Salida: -3, 1
Explicación:
De la array dada, la suma de -3 y 1 es igual a -2 (= X).Entrada: arr[] = {1, -2, 1, 0, 5}, X = 0
Salida: -1
Enfoque: el problema dado se puede resolver mediante la clasificación y la búsqueda binaria . La idea es ordenar la array A[] y, para cada elemento de la array A[i] , buscar si hay otro valor (X – A[i]) presente en la array o no. Siga los pasos a continuación para resolver el problema:
- Ordene la array dada arr[] en orden creciente .
- Atraviese el arreglo arr[] y para cada elemento del arreglo A[i] , inicialice dos variables bajo y alto como 0 y (N – 1) respectivamente. Ahora, realice la búsqueda binaria según los siguientes pasos:
- Si el valor en el índice medio de la array arr[] es (X – A[i]) , imprima este par actual y salga del bucle .
- Actualizar mid as (low + high)/2 .
- Si el valor de A[mid] es menor que X , actualice bajo como (mid + 1) . De lo contrario, actualice alto como (mid – 1) .
- Después de completar los pasos anteriores, si no se encuentra dicho par, imprima -1 .
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 check if the array has
// 2 elements whose sum is equal to
// the given value
void hasArrayTwoPairs(int nums[],
int n, int target)
{
// Sort the array in increasing order
sort(nums, nums + n);
// Traverse the array, nums[]
for (int i = 0; i < n; i++) {
// Store the required number
// to be found
int x = target - nums[i];
// Perform binary search
int low = 0, high = n - 1;
while (low <= high) {
// Store the mid value
int mid = low
+ ((high - low) / 2);
// If nums[mid] is greater
// than x, then update
// high to mid - 1
if (nums[mid] > x) {
high = mid - 1;
}
// If nums[mid] is less
// than x, then update
// low to mid + 1
else if (nums[mid] < x) {
low = mid + 1;
}
// Otherwise
else {
// If mid is equal i,
// check mid-1 and mid+1
if (mid == i) {
if ((mid - 1 >= 0)
&& nums[mid - 1] == x) {
cout << nums[i] << ", ";
cout << nums[mid - 1];
return;
}
if ((mid + 1 < n)
&& nums[mid + 1] == x) {
cout << nums[i] << ", ";
cout << nums[mid + 1];
return;
}
break;
}
// Otherwise, print the
// pair and return
else {
cout << nums[i] << ", ";
cout << nums[mid];
return;
}
}
}
}
// If no such pair is found,
// then print -1
cout << -1;
}
// Driver Code
int main()
{
int A[] = { 0, -1, 2, -3, 1 };
int X = -2;
int N = sizeof(A) / sizeof(A[0]);
// Function Call
hasArrayTwoPairs(A, N, X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if the array has
// 2 elements whose sum is equal to
// the given value
static void hasArrayTwoPairs(int nums[],
int n, int target)
{
// Sort the array in increasing order
Arrays.sort(nums);
// Traverse the array, nums[]
for (int i = 0; i < n; i++) {
// Store the required number
// to be found
int x = target - nums[i];
// Perform binary search
int low = 0, high = n - 1;
while (low <= high) {
// Store the mid value
int mid = low
+ ((high - low) / 2);
// If nums[mid] is greater
// than x, then update
// high to mid - 1
if (nums[mid] > x) {
high = mid - 1;
}
// If nums[mid] is less
// than x, then update
// low to mid + 1
else if (nums[mid] < x) {
low = mid + 1;
}
// Otherwise
else {
// If mid is equal i,
// check mid-1 and mid+1
if (mid == i) {
if ((mid - 1 >= 0)
&& nums[mid - 1] == x) {
System.out.print(nums[i] + ", ");
System.out.print( nums[mid - 1]);
return;
}
if ((mid + 1 < n)
&& nums[mid + 1] == x) {
System.out.print( nums[i] + ", ");
System.out.print( nums[mid + 1]);
return;
}
break;
}
// Otherwise, print the
// pair and return
else {
System.out.print( nums[i] + ", ");
System.out.print(nums[mid]);
return;
}
}
}
}
// If no such pair is found,
// then print -1
System.out.print(-1);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 0, -1, 2, -3, 1 };
int X = -2;
int N = A.length;
// Function Call
hasArrayTwoPairs(A, N, X);
}
}
// This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to check if the array has # 2 elements whose sum is equal to # the given value def hasArrayTwoPairs(nums, n, target): # Sort the array in increasing order nums = sorted(nums) # Traverse the array, nums[] for i in range(n): # Store the required number # to be found x = target - nums[i] # Perform binary search low, high = 0, n - 1 while (low <= high): # Store the mid value mid = low + ((high - low) // 2) # If nums[mid] is greater # than x, then update # high to mid - 1 if (nums[mid] > x): high = mid - 1 # If nums[mid] is less # than x, then update # low to mid + 1 elif (nums[mid] < x): low = mid + 1 # Otherwise else: # If mid is equal i, # check mid-1 and mid+1 if (mid == i): if ((mid - 1 >= 0) and nums[mid - 1] == x): print(nums[i], end = ", ") print(nums[mid - 1]) return if ((mid + 1 < n) and nums[mid + 1] == x): print(nums[i], end = ", ") print(nums[mid + 1]) return break # Otherwise, print the # pair and return else: print(nums[i], end = ", ") print(nums[mid]) return # If no such pair is found, # then print -1 print (-1) # Driver Code if __name__ == '__main__': A = [0, -1, 2, -3, 1] X = -2 N = len(A) # Function Call hasArrayTwoPairs(A, N, X) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if the array has
// 2 elements whose sum is equal to
// the given value
static void hasArrayTwoPairs(int[] nums, int n, int target)
{
// Sort the array in increasing order
Array.Sort(nums);
// Traverse the array, nums[]
for (int i = 0; i < n; i++)
{
// Store the required number
// to be found
int x = target - nums[i];
// Perform binary search
int low = 0, high = n - 1;
while (low <= high)
{
// Store the mid value
int mid = low + ((high - low) / 2);
// If nums[mid] is greater
// than x, then update
// high to mid - 1
if (nums[mid] > x) {
high = mid - 1;
}
// If nums[mid] is less
// than x, then update
// low to mid + 1
else if (nums[mid] < x) {
low = mid + 1;
}
// Otherwise
else {
// If mid is equal i,
// check mid-1 and mid+1
if (mid == i) {
if ((mid - 1 >= 0) && nums[mid - 1] == x) {
Console.Write(nums[i] + ", ");
Console.Write( nums[mid - 1]);
return;
}
if ((mid + 1 < n) && nums[mid + 1] == x) {
Console.Write( nums[i] + ", ");
Console.Write( nums[mid + 1]);
return;
}
break;
}
// Otherwise, print the
// pair and return
else {
Console.Write( nums[i] + ", ");
Console.Write(nums[mid]);
return;
}
}
}
}
// If no such pair is found,
// then print -1
Console.Write(-1);
}
// Driver Code
static public void Main (){
int[] A = { 0, -1, 2, -3, 1 };
int X = -2;
int N = A.Length;
// Function Call
hasArrayTwoPairs(A, N, X);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program for the above approach
// Function to check if the array has
// 2 elements whose sum is equal to
// the given value
function hasArrayTwoPairs(nums, n, target)
{
// Sort the array in increasing order
nums.sort();
var i;
// Traverse the array, nums[]
for (i = 0; i < n; i++) {
// Store the required number
// to be found
var x = target - nums[i];
// Perform binary search
var low = 0, high = n - 1;
while (low <= high) {
// Store the mid value
var mid = low
+ (Math.floor((high - low) / 2));
// If nums[mid] is greater
// than x, then update
// high to mid - 1
if (nums[mid] > x) {
high = mid - 1;
}
// If nums[mid] is less
// than x, then update
// low to mid + 1
else if (nums[mid] < x) {
low = mid + 1;
}
// Otherwise
else {
// If mid is equal i,
// check mid-1 and mid+1
if (mid == i) {
if ((mid - 1 >= 0)
&& nums[mid - 1] == x) {
document.write(nums[i] + ", ");
document.write(nums[mid - 1]);
return;
}
if ((mid + 1 < n) && nums[mid + 1] == x) {
document.write(nums[i] + ", ");
document.write(nums[mid + 1]);
return;
}
break;
}
// Otherwise, print the
// pair and return
else {
document.write(nums[i] +", ");
document.write(nums[mid]);
return;
}
}
}
}
// If no such pair is found,
// then print -1
document.write(-1);
}
// Driver Code
var A = [0, -1, 2, -3, 1];
var X = -2;
var N = A.length;
// Function Call
hasArrayTwoPairs(A, N, X);
</script>
Producción:
-3, 1
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Enfoques alternativos: consulte la publicación anterior de este artículo para conocer más enfoques para resolver este problema.
Publicación traducida automáticamente
Artículo escrito por nadendlaavinash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA