Given an array arr[] consisting of N integers, and an integer X, the task is to find two elements from the array arr[] having sum X. If there doesn’t exist such numbers, then print “-1”.
Examples:
Input: arr[] = {0, -1, 2, -3, 1}, X = -2
Output: -3, 1
Explanation:
From the given array the sum of -3 and 1 is equal to -2 (= X).Input: arr[] = {1, -2, 1, 0, 5}, X = 0
Output: -1
Approach: The given problem can be solved by using sorting and binary search, The idea is to sort the array A[] and for each array element A[i], search whether there is another value (X – A[i]) present in the array or not. Follow the steps below to solve the problem:
- Sort the given array arr[] in increasing order.
- Traverse the array arr[] and for each array element A[i], initialize two variables low and high as 0 and (N – 1) respectively. Now, perform the Binary Search as per the following steps:
- If the value at index mid in the array arr[] is (X – A[i]), then print this current pair and break out of the loop.
- Update mid as (low + high)/2.
- If the value of A[mid] is less than X, then update low as (mid + 1). Otherwise, update high as (mid – 1).
- After completing the above steps, if no such pair is found, then print -1.
Below is the implementation of the above approach:
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 valuevoid 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 Codeint 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 approachimport 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 valuedef 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 Codeif __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 approachusing 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 valuefunction 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> |
Output:
-3, 1
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Alternate Approaches: Refer to the previous post of this article to know about more approaches to solve this problem.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
