Wednesday, July 18, 2012

1- (Array question) Given an integer array, output all pairs that sum up to a specific value k.

You may want to check the original post with more comprehensive explanation from here.

/*
 * Given an integer array, output all pairs that sum up to a specific value k.
 */
package pkg1arraypairsum;

import java.util.Arrays;

//Non-static method cannot be referenced from a static context
//requires an instance of the X class in order to call it
public class Main {

    static int currentSum;

    public static void main(String[] args) {
        Integer[] array = {0, 3, 2, 12, 4, 5};

        long lStartTime = System.nanoTime(); //start time
        pairSum(array, 6); //method execute
        long difference = System.nanoTime() - lStartTime; //check difference
        System.out.println("Elapsed value of the most precise available system time: " + difference);
    }
    //Complexity: O(NlogN)

    public static void pairSum(Integer[] array, int k) {
        if (array.length < 2) {
            return;
        }
        Arrays.sort(array);
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            currentSum = array[left] + array[right];
            if (currentSum == k) {
                System.out.println(array[left] + " " + array[right]);
                left += 1;//or  right-=1;
            } else if (currentSum < k) {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
    // is it possible to reduce the complexity O(N)?
    // Yes
}
Output