Google

Apr 28, 2014

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

Labels: ,

3 Comments:

Anonymous Anonymous said...

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

7:28 PM, May 10, 2014  
Blogger Cathy Liu said...

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

1:51 AM, June 12, 2014  
Blogger bhushan said...

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

4:44 AM, July 28, 2014  

Post a Comment

Subscribe to Post Comments [Atom]

Links to this post:

Create a Link

<< Home