### Core Java coding question to find 2 numbers from an array that add up to the target

## Core Java Coding Questions and Answers for beginner to intermediate level

Q1 | Q2 | Q3 | Q4 | Q5 - Q8 | Q9 | Q10 | Q11 | Q12 - Q14 | Q15 |

**Q**. Given an array of integers, find two numbers such that they add up to a specific target number?

For example,

**Given numbers**: {2, 3, 8, 7, 5}

**Target number**: 9

**Result**: 2 and 7

**A**. There are naive algorithms like using a for loop within a for loop with

**O(n^2) complexity**. Let's look at more efficient solutions.

**Solution 1:**Store processed numbers in a set.

Here is the code

package com.java8.examples; import java.util.HashSet; import java.util.Iterator; import java.util.Set; import javax.management.RuntimeErrorException; public class Sum2NumsToATargetNumberTest { public static int[] findNumsThatSumToTargetNum(int[] numbers, int target) { Set<Integer> processedNumbers = new HashSet<>(); boolean foundSum = false; int[] result = new int[2]; for (int i = 0; i < numbers.length; i++) { int reqNumber = target - numbers[i]; System.out.println("current number=" + numbers[i] + " , requiredNumber = " + reqNumber); if(processedNumbers.contains(reqNumber)){ result[0] = numbers[i]; result[1] = reqNumber; foundSum = true; break; } else { processedNumbers.add(numbers[i]); } } if(!foundSum){ throw new RuntimeException("Sum is not found !!"); } return result; } }The main method to test:

public static void main(String[] args) { int[] numbers = {2, 3, 8, 7, 5}; int target = 9; int[] result = findNumsThatSumToTargetNum(numbers, target); System.out.println("Two numbers that add up to " + target + " are " + result[0] + " and " + result[1]); }

**Output**:

current number=2 , requiredNumber = 7

current number=3 , requiredNumber = 6

current number=8 , requiredNumber = 1

current number=7 , requiredNumber = 2

Two numbers that add up to 9 are 7 and 2

**Solution 2:**Sort the numbers and use 2 pointers.

package com.java8.examples; import java.util.Arrays; public class Sum2NumsToATargetNumberTest2 { public static void main(String[] args) { int[] numbers = {2, 3, 8, 7, 5}; int target = 9; int[] result = findNumsThatSumToTargetNum(numbers, target); System.out.println("Two numbers that add up to " + target + " are " + result[0] + " and " + result[1]); } // System.out.println("current number=" + numbers[i] + " , requiredNumber = " + reqNumber); static int[] findNumsThatSumToTargetNum(int[] numbers, int target) { int pointer1 = 0; int pointer2 = numbers.length -1; int[] result = new int[2]; Arrays.sort(numbers); // sort the numbers while(pointer2 >= pointer1) { int sum = numbers[pointer1] + numbers[pointer2]; if(sum == target) { result[0] = numbers[pointer1] ; result[1] = numbers[pointer2] ; break; } //if sum is greater than the target if(sum > target) { pointer2--; //move pointer2 to the left to reduce the sum } //if sum is less than the target if(sum < target) { pointer1++; //move pointer1 to the right to increase the sum } } return result; } }

**Output**:

Two numbers that add up to 9 are 2 and 7

## 3 Comments:

1. Store the array in a hashmap with key=a[i] and value=i (index) being the same i.e. {(2,1), (3,2) ......}

2. Scan the array

3. For each element get diff = Desired Value - a[i]

4. check if diff exists in hashmap. => map.get(diff)

5. If present return (a[i] and a[map.get(diff)]

5. If present then return

keys of hashmap/hashset are not necessarily sorted, so the worst case (no pair found) run time of this hash implementation is still O(n^2).

In the worst case (no pair found):

for the last element (nth element), compare with all previous elements n-1 times,

for the second to last element (n-1 element), compare n-2 times

so the number of comparison is (n-1) + (n-2) + (n-3).... which is the same as 1+ 2 + 3... + n, which is (n+1)(n/2), I guess half of n^2 is better than n^2, but hashing the values doesn't necessarily generate linear run time

Using list:

List nums = Arrays.asList(num);

for(int i : nums)

{

int s1 = value - i;

if( nums.indexOf(s1) != -1 )

{

System.out.println(i + " " + s1);

break;

}

}

## Post a Comment

Subscribe to Post Comments [Atom]

## Links to this post:

Create a Link

<< Home