Tuesday 22 September 2015

Two numbers sum up to k

Problem

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

Solution

We put two pointers at two ends of the array. As the array is sorted, if the sum is less than k, then by moving left pointer right side will increase the sum. If the sum exceeds k, we can move the right pointer to the left. The complexity is O(n). This is possible, because the array is sorted, we will discuss some other way in our next program where this complexity can be reached when the array is not sorted.

Code

public class TwoSumToK
{
 public static void main(String[] args)
 {
  int[]arr={1,2,3,4,5,6,7,8,9,12,13,14,16,32,44};
  printIndexesForSumK(arr, 16);
 }
 
 public static void printIndexesForSumK(int[]arr,int k)
 {
  int startIndex=0;
  int endIndex=arr.length-1;
  while(startIndex<endIndex)
  {
   int sum=arr[startIndex]+arr[endIndex];
   if(sum==k)
   {
    System.out.println(arr[startIndex]+","+arr[endIndex]);
    startIndex++;
    endIndex--;
   }
   else if (sum<k)
    startIndex++;
   else if(sum>k)
    endIndex--;
  }
 }

}
        

No comments:

Post a Comment