In this article we are going to discuss a problem from arrays; this is one of the most commonly asked interview question of today.
 

For a given array of integers, you have to find all pairs of elements in this array whose sum is equals to a given number..

e.g. if {4, 5, 7, 11, 9, 13, 8, 12} is an array and 20 is the given number, then you have to find all pairs of elements in this array whose sum must be 20. In this example, (9, 11), (7, 13) and (8, 12) are such pairs whose sum is 20.
Solution 1: Using two loops

We can find the easiest solution by iterating over over all the elements and trying to add the number with all other elements in the array, when the sum is equals to the targeted number we print that. Here is the solution:

	public void withTwoLoops(int[] inputArray, int targetNumber) {
		// iterating through the array 
		for (int i = 0; i < inputArray.length; i++) {
			// iterating through all other elements to add with arr[i]
			for (int j = i + 1; j < inputArray.length; j++) {
				// if sum is targeted number print the value
				if (inputArray[i] + inputArray[j] == targetNumber)
					System.out.println(inputArray[i] + " + " + inputArray[j]
							+ " = " + targetNumber);

			}
		}
	}

Output:

4 + 6 = 10
5 + 5 = 10
-10 + 20 = 10


Solution 2: Using one loop only

In previous solution the time complexity is O(n2) and so not good for arrays of big size. If the given array is already sorted, we can find the solution using single loop only. The complexity of this solution is O(nlogn) and hence convenient for big arrays. See the example below:

		public void withSingleLoops(int[] inputArray, int targetNumber) {

		Arrays.sort(inputArray);

		// start index
		int start = 0;
		
		// end index
		int end = inputArray.length - 1;

		// loop through the array until all elements are exhausted 
		while (start < end) {
			if (inputArray[start] + inputArray[end] == targetNumber) {
				System.out.println(inputArray[start] + " + " + inputArray[end]
						+ " = " + targetNumber);
				start++;
				end--;
			} else if (inputArray[start] + inputArray[end] > targetNumber)
				end--;
			else
				start++;

		}
	}

Output

4 + 6 = 10
5 + 5 = 10
-10 + 20 = 10


Complete program

Here is complete program for the problem statement, you can try it out by coping in your local Java environment.

package com.techburps.byexample;

import java.util.Arrays;

public class ArrayExample {

	public static void main(String[] args) {
		int[] inputArray = { 4, 6, 5, -10, 8, 5, 20 };
		int targetNumber = 10;

		ArrayExample arrayExample = new ArrayExample();
		arrayExample.withTwoLoops(inputArray, targetNumber);

	}

	public void withTwoLoops(int[] inputArray, int targetNumber) {
		// iterating through the array 
		for (int i = 0; i < inputArray.length; i++) {
			// iterating through all other elements to add with arr[i]
			for (int j = i + 1; j < inputArray.length; j++) {
				// if sum is targeted number print the value
				if (inputArray[i] + inputArray[j] == targetNumber)
					System.out.println(inputArray[i] + " + " + inputArray[j]
							+ " = " + targetNumber);

			}
		}
	}

	public void withSingleLoops(int[] inputArray, int targetNumber) {

		Arrays.sort(inputArray);

		// start index
		int start = 0;
		
		// end index
		int end = inputArray.length - 1;

		// loop through the array until all elements are exhausted 
		while (start < end) {
			if (inputArray[start] + inputArray[end] == targetNumber) {
				System.out.println(inputArray[start] + " + " + inputArray[end]
						+ " = " + targetNumber);
				start++;
				end--;
			} else if (inputArray[start] + inputArray[end] > targetNumber)
				end--;
			else
				start++;

		}
	}
}


That?s it, we have seen how to find pair of elements in an array whose sum is equals to a given number. In upcoming articles we will see more about Java and Related programming problems and solutions.
  • By Techburps.com
  • Apr 12, 2015
  • Programming