Check for pairs in an array with a particular sum

Posted in

Check for pairs in an array with a particular sum
vinaykhatri

Vinay Khatri
Last updated on May 30, 2024

    Consider an array arr[] with n elements where the values in the array consist of both positive values and negative values, including zero. Consider a number x. Find out whether the value x can be formed by adding any two values from the given array arr[].

    Example 1

    Input:
    Consider the array arr[] = {8,5,1,0}
    Let n = 9
    Output:  8,1

    Explanation: For the given array, the value n=9 can be formed by adding the array values 8 and 1 which are index positions 0,2, respectively.

    Example 2

    Input:
    Consider the array arr[][] = {-6,0,7,-9,5,2}
    Let n = 10
    Output: Not Possible.

    Explanation For the given array arr[], the value n=10 cannot be formed by considering any pair together.

    Example 3 Input:

    Consider the array arr[][] = {-1,12,28,7,6,-2}
    Let n = 26
    Output: 28,-2

    Explanation: For the given array, the value n=26 can be formed by adding the array values 28 and -2 which are at index positions 2,5, respectively. 28 + (-2) =26

    Approach 1:  Using Pointers

    Initially, sort the given array in ascending order and initialize two pointers such that a pointer points to the first element of the sorted array and another pointer points to the last element of the sorted array. Here comes the actual logic, if the sum of the two pointer elements’ values is greater than the required sum, then decrement the right side pointer.

    If the sum of the two pointer elements is lesser than the required sum, then increment the left side pointer such that it points to the next element. Follow the same process till we find the required sum. If the two pointers point to the same element, then return 0 as the required sum cannot be obtained from the given array.

    Algorithm

    1. Initialize the array size and take the array values into the array.
    2. Sort the array in increasing order. Use any sorting method to sort the array.
    3. Now consider two variables -  beg and end.
      1. Initialize beg = 0.
      2. Initialize end = array_size-1.
    4. Traverse the entire array until the required sum is found, and use the sum of the beg, and end variables to sum the elements.
      1. If the sum equal to the required sum is found, then return 1.
      2. If the sum is greater than the required sum, then decrement the end.
      3. If the sum is less than the required sum, then increment the beg.
    5. If the required sum is not found even after traversing the entire array, then return 0.

    The implementation of the approach discussed above is as follows.

    C++ Code

    #include <bits/stdc++.h>
    using namespace std;
    //arraychecker function to check the 2 values
    bool arraychecker(int arr[], int array_size,int sum)
    {
      int beg,end;
        //Sorting the array in ascending order
      sort(arr, arr + array_size);
     
      //Finding the required values to get the required sum
      beg = 0;
      end = array_size - 1;
      while (beg < end) {
        if (arr[beg] + arr[end] == sum)
          return 1;
        else if (arr[beg] + arr[end] < sum)
          beg++;
        else 
          end--;
      }
      return 0;
    }
     
    //Driver Code
    int main()
    {
      int arr[] = { 12,28,7,6 };
      int sum = 18;
      int array_size = sizeof(arr) / sizeof(arr[0]);
     
      // Calling arraychecker function
      if (arraychecker(arr, array_size, sum))
        cout << "Required sum can be obtained using the given array elements";
      else
        cout << "Required sum cannot be obtained using the given array elements";
    }
    

    Output

    C# Code

    using System;
    class Program {
    	static bool arraychecker(int[] arr,int array_size, int sum)
    	{
    		int beg, end;
    
    		// Sorting array elements
    		sort(arr, 0, array_size - 1);
    
    		beg = 0;
    		end = array_size - 1;
    		
    		while (beg < end) 
    		{
    			if (arr[beg] + arr[end] == sum)
    				return true;
    			else if (arr[beg] + arr[end] < sum)
    				beg++;
    			else 
    				end--;
    		}
    		return false;
    	}
    
    	static int fun1(int[] arr, int low, int high)
    	{
    	    int i,j,t,pivot,t1;
    		pivot = arr[high];
    		i = (low - 1);
    		for(j = low; j <= high - 1; j++) 
    		{
    			if (arr[j] <= pivot) 
    			{
    				i++;
    				t = arr[i];
    				arr[i] = arr[j];
    				arr[j] = t;
    			}
    		}
    
            t1 = arr[i + 1];
    		arr[i + 1] = arr[high];
    		arr[high] = t1;
    
    		return i + 1;
    	}
    
    	static void sort(int[] arr, int low, int high)
    	{
    		if (low < high) {
    			int pi = fun1(arr, low, high);
    			sort(arr, low, pi - 1);
    			sort(arr, pi + 1, high);  //Sorting elements in recursive manner
    		}
    	}
    
    	// Driver code
    	public static void Main()
    	{
    		int[] arr = { 12,28,7,6 };
    		int sum = 18;
    		int array_size = 4;
    
    		if (arraychecker(arr, array_size, sum))
    			Console.Write("Required sum can be obtained using the given array elements");
    		else
    			Console.Write("Required sum cannot be obtained using the given array elements");
    	}
    }
    

    Output:

    Java Code

    import java.util.*;
    
    class Main {
    	static boolean arraychecker(int arr[],int array_size, int sum)
    	{
    		int beg, end;
    
    		// Sort the array in increasing order
    		Arrays.sort(arr);
    		beg = 0;
    		end = array_size - 1;
    		while (beg<end) {
    			if (arr[beg] + arr[end] == sum)
    				return true;
    			else if (arr[beg] + arr[end] < sum)
    				beg++;
    			else 
    				end--;
    		}
    		return false;
    	}
    	// Driver Code
    	public static void main(String args[])
    	{
    		int arr[] = { 12,28,7,6 };
    		int sum = 18;
    		int array_size = arr.length;
    
    		// calling arraychecker function
    		if (arraychecker(arr, array_size, sum))
    			System.out.println("Required sum can be obtained using the given array elements");
    		else
    			System.out.println("Required sum cannot be obtained using the given array elements");
    	}
    }
    

    Output

    Python Code

    def arraychecker(arr, arr_size, sum):
        #Sorting the array in increasing order
        quickSort(arr, 0, arr_size-1)
        beg = 0
        end = arr_size-1
    
        # finding the two elements to get the required sum
        while beg

    Output

    Complexity Analysis

    Time Complexity: In the worst case, it takes O(n^2) as we have used Quick Sort.

    Space Complexity: It takes O(n) for merge sort.

    Approach 2: Using remainders of the array elements

    In this approach, from the given array of elements, we pick the elements which are less than the required sum. Now we perform a modulo operation with these numbers and the required sum. We calculate the remainders because the remainders give the required sum. Now we will calculate the remainder of these elements.

    Consider the array,   Arr[] = {1, 4, 45, 6, 10} Required sum = 16   From the given array pick the numbers which are less than 16. So the elements would be 1,4,6,10,-8.   We need to get the remainder of these values. To get the remainders, we perform the modulo operation: So,  ( 1%16 )  = 1 ( 4%16 ) = 4 ( 6%16 ) = 6 ( 10%16 ) = 10

    Algorithm

    1. Initialize the array with all the elements.

    2. Initialize all the remaining elements to zero.

    3. Now, traverse through the entire array.

        If arr[i] is less than the sum:
                 Rem = arr[i]%x  // this gives the remainder for the values.
                 Rem[r] = rem[r]+1  //it increases the count of elements if it has same remainder.

    4. Now start traversing the remainder array from starting to middle

      If rem[i]>0 and rem[i-1]>0:
                Print Yes // as we found the required pair of elements.

    5. If the pair is not found in the above step, then it means that we have traversed from the start to the middle of the array. As of now, we are at the middle of the array,             a. if x is even:

                               If rem[x/2] > 1: // if we found two elements with rem x/2
                                          Print Yes else print No.

    b. if x is odd:

                                If rem[x/2]>1 and rem[x-x/2]>1: //as x is odd 2, we are checking for two elements
                                            Print Yes else print No.

    C++ Code

    #include <iostream>
    using namespace std;
    //numbers function
    void numbers(int arr[], int sum, int x)
    {
      int i;
      int rem[x];
      for (i = 0; i < x; i++)
      {
        //initializing rem with 0's
        rem[i] = 0;
      }
      for (i = 0; i < sum; i++)
      {
        if (arr[i] < x)
        {
          rem[arr[i] % x]++;
        }
      }
      //Traversing After reaching middle
      for (i = 1; i < x / 2; i++) { if (rem[i] > 0 && rem[x - i] > 0)
        {
            cout << "Required sum can be obtained using the given array elements"<< "\n"; break; } } if (i >= x / 2)
      {
        if (x % 2 == 0)
        {
          if (rem[x / 2] > 1)
          {
                    //If x is even
            cout << "Required sum can be obtained using the given array elements"<< "\n";
          }
          else
          {
            cout << "Required sum cannot be obtained using the given array elements"<< "\n"; } } else { //If x is odd if (rem[x / 2] > 0 &&
            rem[x - x / 2] > 0)
          {
            cout << "Required sum can be obtained using the given array elements"<< "\n";
          }
          else
          {
            cout << "Required sum cannot be obtained using the given array elements"<< "\n";
          }
        }
      }
    }
    
    //Driver Code
    int main()
    {
      int arr[] = { 12,28,7,6 };
      int sum = 18;
      int arr_size = sizeof(arr) / sizeof(arr[0]);
      // Function calling
      numbers(arr, arr_size, sum);
    

    Output

    C# Code

    using System;
    class program
    {
    static void arraychecker(int []arr, int n, int x)
    {
    int i;
    int []rem = new int[x];
    for (i = 0; i < x; i++)
    {
        //initializing rem with 0's	
    	rem[i] = 0;
    }
    for (i = 0; i < n; i++)
    {
    	if (arr[i] < x)
    	{
    	rem[arr[i] % x]++; // updating the count of the numbers
    	}
    }
    
    //Traversing the array from start to end
    for (i = 1; i < x / 2; i++) { if (rem[x-i] > 0 && rem[i] > 0)
    	{
    	Console.Write("Required sum can be obtained using the given array elements");
    	break;
    	}
    }
    
    if (i >= x / 2)  //At middle of the array
    {
    	if (x % 2 == 0)
    	{
        	if (rem[x / 2] > 1)
        	{
        
        		Console.Write("Required sum can be obtained using the given array elements"); // if x is even
        	}
        	else
        	{
        		Console.Write("Required sum cannot be obtained using the given array elements");
        	}
    	}
    	else // if x is odd  
    	{ 
        	if (rem[x / 2] > 0 &&	rem[x - x / 2] > 0)
        	{
        		Console.Write("Required sum can be obtained using the given array elements");
        	}
        	else
        	{
        		Console.WriteLine("Required sum cannot be obtained using the given array elements");
        	}
    	}
    }
    }
    
    // Driver Code
    public static void Main(string[] args)
    {
    	int[] arr = { 12,28,7,6 };
    	int sum = 18;
    	int array_size = arr.Length;
    	
    	// Calling the function arraychecker
    	arraychecker(arr, array_size, sum);
    }
    }
    

    Output

    Java Code

    import java.util.*;
    class Main
    {
        static void numbers(int arr[], int sum, int x)
        {
            int i;
            int []rem = new int[x];
            
            //rem with all 0's
            for (i = 0; i < x; i++)
            {
                rem[i] = 0;
            }
            for (i = 0; i < sum; i++)
            {
                if (arr[i] < x)
                {
                    rem[arr[i] % x]++;
                }
            }
            
            // finding  pairs by traversing through the remainder list
            for (i = 1; i < x / 2; i++) { if (rem[i] > 0 && rem[x - i] > 0)
                {
                System.out.print("Required sum can be obtained using the given array elements");
                break;
                }
            }
            
            //After reaching middle of array
            if (i >= x / 2)
            {
                if (x % 2 == 0)
                {
                    if (rem[x/2] > 1)
                     {
                        System.out.print("Required sum can be obtained using the given array elements");
                     }
                    else
                     {
                        System.out.print("Required sum cannot be obtained using the given array elements");
                     }
                }
                else
                {
                    //if x is odd
                    if (rem[x/2] > 0 && rem[x-x/2] > 0)
                     {
                        System.out.print("Required sum can be obtained using the given array elements");
                     }
                    else
                     {
                        System.out.print("Required sum cannot be obtained using the given array elements");
                     }
                }
        }
    }
    
    //Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 12,28,7,6 };
        int sum = 18;
        int array_size = arr.length;
    
        // Function calling
        numbers(arr, array_size, sum);
    }
    }
    

    Output

    Python Code

    def numbers(arr, sum, x):
        rem = []
        for i in range(x):
            # adding 0's to rem
            rem.append(0)
        for i in range(sum):
            if (arr[i] < x): rem[arr[i] % x] += 1 # Traversing from start to middle for i in range(1, x // 2): if (rem[i] > 0 and rem[x - i] > 0):
                print("Required sum can be obtained using the given array elements")
                break
        #After reaching middle of array
        if (i >= x // 2):
            if (x % 2 == 0):
                if (rem[x // 2] > 1): # if x is even
                    print("Required sum can be obtained using the given array elements")
                else:
                    print("Required sum cannot be obtained using the given array elements")
            else: # if x is odd
                if (rem[x // 2] > 0 and rem[x - x // 2] > 0):
                    print("Required sum can be obtained using the given array elements")
                else:
                    print("Required sum cannot be obtained using the given array elements")
    
    # Driver Code
    arr = [ 12,28,7,6 ]
    sum = 18
    arr_size = len(arr)
    
    # calling the numbers function
    numbers(arr, arr_size, sum)
    

    Output

    Complexity Analysis

    Time Complexity : It takes O(n+x) time complexity.

    Space Complexity : It requires only O(x) complexity.

    Conclusion

    In this article, we have discussed how to check if there are any pairs of numbers that sum up to a given value. The logic is discussed in two approaches, where one approach uses the concept of pointers and another approach uses a hashmap data structure. We have also discussed the algorithm, and code implementation in c++, Java, Python, and  C# for both approaches. We hope this article helps you to solve this problem and its variants in a better and more efficient way.

    Happy Coding!

    People are also reading:

    Leave a Comment on this Post

    0 Comments