Check for pairs in an array with a particular sum

By | June 7, 2021

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

Vamware
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, use the sum of the beg, 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 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 remainders 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 remainders 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 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 pair 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, 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 efficient way.

Happy Coding!

Leave a Reply

Your email address will not be published. Required fields are marked *