Find a pair in array whose sum is x

Let’s write a program to find pair in array whose sum is equal to given number. We can achieve this by using two methods: by sorting & without sorting.

Find a pair in array whose sum is equal to given number by using Sorting

Steps:

  1.      First sort the array.

  2.      Initialize left and right indexes as l = 0, r = arr.length – 1

  3.      Loop the array until l < r

  4.      Verify arr[l] + arr[r] is less than sum, then increase l

  5.      Verify arr[l] + arr[r] is greater than sum, then decrease r.

  6.      If arr[l] + arr[r] is equal to sum then return true, if not return false.

Example explanation:

  ·        Given array is : {5, 4, 2, 8}, sum is 9.

  ·        Sort the array: { 2, 4, 5, 8}

  ·        Initialize l = 0 and r = 3

  ·        arr[0] + arr[3] à 2+8 > 9 , then decrement “r”. Now r = 2

  ·        arr[0] + arr[2] à 2+5 < 9 , then increment “l”. Now l = 1

  ·        arr[1] + arr[2] à 4+5 == 9, then return true.

import java.util.Arrays;

import java.util.HashSet;

import java.util.Scanner;

public class PairInArray {

      public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);

           

            int[] arr = {5, 4, 2, 8};

           

            System.out.print("Enter sum: ");

            int sum = sc.nextInt();

           

            System.out.println("is pair found : " +isPairFindInArray(arr, sum) );

      }

     

      public static boolean isPairFindInArray(int[] arr, int sum) {

            boolean isFound = false;

            int l=0, r=arr.length-1;

           

            Arrays.sort(arr); // Sorting array elements

           

            while(l < r) {

                  if( (arr[l] + arr[r]) < sum )

                        l++;

                  else if( (arr[l] + arr[r]) > sum )

                        r--;

                  else {

                        isFound = true;

                        break;

                  }

            }          

           

            return isFound;

      }

}

Output:

Enter sum: 9

is pair found : true

Find a pair in array whose sum is equal to given number without Sorting

Steps:

  1.      Loop the array elements.

  2.      Subtract the array element from sum and store in the set.

  3.      Verify is set contains array element or not?

  4.      If yes, return true else return false.

Example Explanation:

  ·        Given array is : {5, 4, 2, 8}, sum is 9.

  ·        Set doesn’t contain arr[0]

  ·        Sum – arr[0] à 9-5 = 4, store in the set.

  ·        Set contains arr[1], return true

import java.util.Arrays;

import java.util.HashSet;

import java.util.Scanner;

public class PairInArray {

      public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);

           

            int[] arr = {5, 4, 2, 8};

           

            System.out.print("Enter sum: ");

            int sum = sc.nextInt();

           

            System.out.println("is pair found : " +isPairFindInArray(arr, sum) );

      }

     

      public static boolean isPairFindInArray(int[] arr, int sum) {

            boolean isFound = false;

            HashSet set = new HashSet();       

           

            for(int i=0; i<arr.length; i++) {

                  if( set.contains(arr[i]) ) {

                        isFound = true;

                        break;

                  }else {

                        set.add( sum - arr[i] );

                  }

            }

           

            return isFound;

      }

}

Output:

Enter sum: 9

is pair found : true