Given an array A[] and a number x, check for pair in A[] with sum as x | Set 2

0 0 7 minutes read

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

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 zambiatek!