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.

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); } } }

4 + 6 = 10

5 + 5 = 10

-10 + 20 = 10

5 + 5 = 10

-10 + 20 = 10

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++; } }

4 + 6 = 10

5 + 5 = 10

-10 + 20 = 10

5 + 5 = 10

-10 + 20 = 10

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

2016 © Techburps. ALL Rights Reserved. Disclaimer Contact Us