Sunday, April 6, 2014

O(n^2) solution to find out if and which 3 of them add up to 0

Here is a O(n^2) solution to find out if and which 3 of them add up to zero.

The Code is in Scala.

/**
 * O(n^2) solution to find out if and which 3 of them add up to 0
 * 
 */
object FindThreeNumbersSumToZero {
  
 def sort(arr:Array[Int]): Array[Int] =   
        if (arr.length<2) arr
        else {
            val pivot = arr (arr.length / 2)
            sort (arr filter (pivot>)) ++ 
            (arr filter (pivot == )) ++ sort (arr filter(pivot <))
        }
 
 def findThreeNumbersAddedToZero (arr: Array[Int]) : (Int, Int, Int) = {

  val a : Array[Int] = sort(arr);
  
  for(i <- 0 until a.length) {
    var iter = i+1;
    var reviter = a.length-1;
    while (iter < reviter) {
      var v = a(i) + a(iter) + a(reviter);
      if (v==0) 
        return (a(i), a(iter), a(reviter));
      else if (v<0)
        iter = iter + 1;
      else 
        reviter = reviter-1;
    }
  }
  return null;
 }
 
   def main(args: Array[String]) {
  
  val arr = Array(-11, 19, -2, 22, -4, 4, 10, 6,  12, 23)
  val tuple = findThreeNumbersAddedToZero (arr);
  println("array is [" + arr.mkString(" ") + "] ");
  println("tuple is " + tuple + "");
  
 }

}




Enjoy the journey. 

No comments:

Post a Comment