Tuesday 22 September 2015

Two numbers sum up to k unsorted

Problem

Given an integer array and an integer k, find two numbers which sum upto k.

Solution

In this unsorted array we can apply the previous algorithm by sorting the array. But that would make our complexity atleast O(n log n). As the best sorting would run in O(n log n) time. We can make the complexity O(n) by using O(n) space. We will store the number in a hashset. and search for the number k-n in the hashset. Whenever the match is found, that means the sum of k is possible by these two numbers. As expected complexity of finding the number in the hashset is O(1) for n such operations total complexity would become O(n)

Code

import java.util.HashSet;


public class UnsortedTwoSumToK
{
 public static void main(String[] args)
 {
  int[]arr={6,7,8,9,1,16,2,3,14,13,4,5,12,32,44};
  printIndexesForSumK(arr, 16);
 }
 
 public static void printIndexesForSumK(int[]arr,int k)
 {
  HashSet<Integer> hashSet=new HashSet<Integer>();
  for(int num:arr)
  {
   if(hashSet.contains(k-num))
    System.out.println(num+","+(k-num));
   hashSet.add(num);
  }
 }

}
        

No comments:

Post a Comment