Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

 Here we have two different algorithms to solve the problem.

Solution One:
Do an in-place merge sort on the array A;
Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
If found, return the pair (A[i], K-A[i]);
If not found, return the null;

Time Complexity: O ( n * log(n) )
Space Complexity: O ( 1 )

Solution Two:
Allocate the array of size K;
Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1
Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
If not found, return the null in the end.

Time Complexity: O ( n )
Space Complexity: O ( K )

The code is in Scala.

/**
 * 
 * Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.
 */

object FindPairSumToK {

 /*
  * Solution One:
  * Do an in-place merge sort on the array A;  
  * Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
  * If found, return the pair (A[i], K-A[i]);
  * If not found, return the null;  
  * 
  * Time Complexity: O ( n * log(n) )
  * Space Complexity: O ( 1 ) 
  */
 def findPairSumToKwithSort(A: Array[Int], K: Int)  : (Int, Int) = {
     mergeSort(A, 0, A.length-1);
     for(i <- 0 until A.length){
       var t : Int = K - A(i);
       if (t>0) {
        var idx : Int = binarySearch(A, t);
        if (idx>=0) {
          return (A(i), A(idx));
        }
       }
     }
     return null;
   }
    
 /*
  * Solution Two:
  * 
  * Allocate the array of size K;
  * Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1    
  * Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
  * If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
  * If not found, return the null in the end.
  * 
  * Time Complexity: O ( n )
  * Space Complexity: O ( K ) 
  *       
  */
 def findPairSumToKwithDynamicProgramming(A: Array[Int], K: Int)  : (Int, Int) = {
        var m: Array[Int] = new Array[Int](K);
        var s : Int = 0;
      while (s<A.length && A(s)>=K) {
        s = s + 1;
      }
      m(A(s)) = 1;
     for(i <- s until A.length){
       var target : Int = K - A(i);
       if (target>=0 && m(target) ==1) {
        return (A(i), target);
       }
     }
     return null;
   }
    
   def reverse(a: Array[Int]): Unit = {
     if (a.length<=1) return;
     
     var i : Int = 0;
     var j : Int = a.length-1;
     while (i<j) {
      a(i) = a(i) + a(j);
      a(j) = a(i) - a(j);
      a(i) = a(i) - a(j);
      i=i+1;
      j=j-1;
    }
 }
   
   def binarySearch(A: Array[Int], target : Int) : Int = {
    var low : Int = 0;
    var high: Int = A.length-1;
    while (low<high) {
     var mid = (low + high) / 2;
     if (target==A(mid)) 
       return mid;
     else if (target<A(mid))
       high = mid-1;
      else 
        low = mid+1;
    }
    return -1;
   }
   
    def mergeSort(a : Array[Int] ) : Unit = {
    mergeSort(a, 0, a.length-1);
 }


    def mergeSort(A: Array[Int], low: Int, high: Int) : Unit = {
  if (low >= high) {
   return;
  }
  var mid = (low + high) / 2;
  mergeSort(A, low, mid);
  mergeSort(A, mid + 1, high);
  merge(A, low, mid, high);
 }

   def merge(a: Array[Int], Low: Int, Mid: Int, High : Int) : Unit = {
    var low = Low;
    var mid = Mid;
    var high = High;

  var i : Int = mid;
  var j : Int = mid + 1;
    while ((low <= i) && (j <= high)) {
   if (a(low) < a(j)) {
    low = low+1;
   } else {
    // shift from j to low
    var t = a(j);
    for (k <- j-1 to (low, -1) ) {
     a(k+1) = a(k);
    }
    a(low) = t;
    low = low + 1;
    i = i+1;
    j = j+1;
   }
    }
   }
   

 def print(a: Array[Int]): Unit = {
    println(a.mkString(" "))
 }
  
 def main(args: Array[String]) {
     
     val a = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     var p = findPairSumToKwithSort(a, 19);
     println("p=" + p);
     p = findPairSumToKwithSort(a, 99);
     println("p=" + p);
     
     val aa = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     p = findPairSumToKwithDynamicProgramming(aa, 19);
     println("p=" + p);
     p = findPairSumToKwithDynamicProgramming(aa, 99);
     println("p=" + p);
 }
}

Enjoy the journey.