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