JAVA : Program To Check If Sum Of Any Two Array Elements Is Equal To A Given Number

Java Code to Check if sum of any two array elements is equal to a given number

Introduction:

This is a very famous and frequent problem when you appear for Online Tests or Technical Interviews for seeking a Job as Software Developer, Software Engineer, etc... As a matter of fact, the programming language which you use to solve this problem is not that important, but the way you approach this problem is certainly important. However, In this article we will try to solve this problem using Java. The same can be achieved using C, C++, C# , Python, etc... Let us directly Jump to the Problem Statement.

Problem Statement:

Write a Program to: 

(a) Accept an array from the user

(b) Accept the Number (Say X - Which is the sum we want by adding two array elements).

(c) Check and inform the user whether the sum is present or not. 

Example: 

Consider the following array :    1    2    5    3    0

First Case:

Enter the required number ( X -which we want as a sum) : 4

Output:

Yes, the sum is present. Reason is 1 + 3 = 4 .

Second Case:

Enter the required number ( X -which we want as a sum) : 9

Output:

No, the sum is not present. Reason being that we do not get 9 as the sum by adding any two elements of the array in any possible way.

Please Note : We strongly recommend that you minimize this window and give it a try to code and solve this problem by yourself .

Approaches  

 

Let us assume we have an array of n elements.

Approach 1 (The Obvious Inefficient Way):

1)  In first Iteration, Add the first element with every other n - 1 elements of the array. If sum is found return 1.If not , move to the next element.

2)  In second Iteration, Add the Second element to the rest of n-2 (excluding first element and the second element itself ) elements of the array. If sum is found return 1 else move to the next element.

3) Continue in the same manner to find whether the sum exists or not.

Approach 2 (The efficient way):

1) Firstly sort the given array.
2)  Add the First (the smallest element) and the last element (the largest element).
3)
    (a) Case 1: If the sum is less than the required number X, move ahead (i.e to the right) to the next element from the left side element. Add the two numbers.
    (b) Case 2: If the sum is larger than the required number X, move to the left to the next element from the right side element. Add the two numbers.
4) Continue till both the left index and right index meet. If sum is found 1 is returned, else 0 is returned.

The following Java Code illustrates the above concept:

//Check if the sum of any two array elements in an array 
//is equal to a given number in an EFFICIENT WAY
package com.array.progs;

import java.io.IOException;
import java.util.Scanner;


class arraySum {

    // Declaring Variables
    private static int n, x, result, temp;
    //Using Scanner class for taking or reading the input form the user
    static Scanner scanner = new Scanner(System.in);

    //simple sorting function to sort the given array
    static void sort(int num[], int n) {
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {

                if (num[i] < num[k]) {
                    temp = num[k];
                    num[k] = num[i];
                    num[i] = temp;
                }
            }
        }
    }
    
    // Function which actually checks whether any two array elements
    // make up the required sum or not. If yes then 1 is returned else
    // 0 is returned means sum was not found
    static int check(int num[], int n,int x) {
    // This check was suggested by our blog reader Eric Hazenberg
    
    // If the sum of first two element of sorted array is greater than
    // than X or if the sum of two last elements of the sorted 
    // array is smaller than X, we should return 0, as no match is possible.
        int l=0,r=n-1;
        if((num[l]+num[l+1] > x) || (num[r-1]+num[r-2] < x))
        return 0;
        while(l<r)
        {
         if(num[l]+num[r] == x) // Sum found, return 1
             return 1;
         else if(num[l]+num[r] < x)
             l++;
         else
             r--;
        }
        return 0; // Sum was not found, return 0
    }

    public static void main(String args[]) throws IOException {
        // Declaring the array
        int[] num;
       //Enter number of array elements
        System.out.println("Enter how many numbers");
        n = scanner.nextInt();
        //Print the number of array elements
        System.out.println("The value of n is: " + n);
        // Dynamically allocating space for an integer array of size n
        num = new int[n];
        //Getting the elements of the array
        for (int i = 0; i < num.length; i++) {
            System.out.println("Enter element for array");
            num[i] = scanner.nextInt();
        }
        //Enter the number whose sum has to be found from array
        System.out.println("Enter the value of X");
        x = scanner.nextInt();
        
        // Firstly, Sort the array
        sort(num, n);
        // Printing the sorted Array
        for(int i=0;i<n;i++)
        {
            System.out.println(num[i]+" ");
        }
        // Chaecking if two array elements make the required sum
        result = check(num, n,x);
        if(result==0)
            System.out.println("Sum is not present");
        else
            System.out.println("Sum is present");
    }
    
    //Constructor [initializes the value of n to be 0]
    arraySum() {
        n = 0;
    }

}

The output would look like:

case 1: When Sum is present.

case 2: When Sum is not present.

Please let us know if you have an even better way of doing this. We will be more than happy to add that approach in this article.We hope you liked the article. Stay tuned for more to come. Cheers!!