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]
<< Home