Java program to check if two elements of an array adds to the given sum

Hi everyone, in this blog post, I will be discussing about a famous java program, which is to check if two elements of an array adds to the given sum.

Problem

Given an array with elements and a sum. Check whether any 2 elements of the array adds to the given sum. Return true if the sum is present, else return false.

Example

Given an array {1,2,4}. The array should return true for the sum 5 and false for 4.

Solution

The basic solution which comes to everyone's mind would be to check each element with each other elements for the given sum. But the total time complexity in doing that will be O(n^2).
We will approach the problem in a much easier way. The logic for that is as follows:

• Sort the given array in ascending order.
• Create two variables, one which tracks from the first position of array (pos_first) and other which tracks from the last position of the array (pos_last).
• While pos_first is less than pos_last, do the below steps.
• Add the elements corresponding to the positions of pos_first and pos_last.
• If sum equals the required sum, return true.
• Otherwise if sum is less than required sum, increment pos_first.
• If sum is greater than required sum, decrement pos_last.
• Return false.

By this method, the overall time complexity will O(nlogn), which is the time complexity for sorting the array. During coding interviews, the interviewers expects us to give the solution in least time complexity.

IDE used - IntelliJ

Java Program

The java program is as follows:

package com.techjourney;

import java.util.Arrays;

/**
 * Created by Sujith Mohan on 3/10/2015.
 */
public class CheckForGivenSumInArray {

    public static void main (String args[])
    {
        int array_1[] = {6,2,9,17,23,8,4,6,22,25,17,14,3,30};
        int array_2[] ={6,-5,4,21,-21,-4,-8,10,30,26,1,1,9,-8};

        System.out.println(returnTrueIfGivenSumIsPresent(array_1, 34));
        System.out.println(returnTrueIfGivenSumIsPresent(array_1, 71));
        System.out.println(returnTrueIfGivenSumIsPresent(array_2, -29));
        System.out.println(returnTrueIfGivenSumIsPresent(array_1, -30));
    }

    public static boolean returnTrueIfGivenSumIsPresent(int arr[], int sum)
    {
        Arrays.sort(arr);
        int pos_first = 0;
        int pos_last=arr.length-1;

        while(pos_first<pos_last)
        {
            if(arr[pos_first]+arr[pos_last]== sum)
            {
                return true;
            }

            else if(arr[pos_first]+arr[pos_last]<sum)
            {
                pos_first++;
            }

            else
            {
               pos_last--;
            }
        }

        return false;
    }

}

In the above program, I have assumed that the array contains at least 2 values. I have used an array containing only positive terms and other array containing positive and negative elements to make sure this program works for all type of elements.

Output

true
false
true
false
Picked up _JAVA_OPTIONS: -Xmx512M

Process finished with exit code 0

I hope everyone understood this program very well. Please comment below if you have any doubts regarding this. Please refer other programs of my blog if you liked this one.

Similar Programs

1) Program to change elements of array with product of remaining elements.
2) Program to find the third largest element in an array.