Write an efficient algorithm to find K-complementary pairs in a given array of integers.

Write an efficient algorithm to find K-complementary pairs in a given array of integers. Given Array A, pair (i, j) is K- complementary if K = A[i] + A[j];
========================================================================
package com.test.arun;

import java.util.Arrays;

/**
 * * Java Program to find all pairs on integer array whose sum is equal to k
 * The complexity of this program would be O(NlogN)
 */
public class ComplementaryPairs {
public static void main(String args[]) {
prettyPrint(new int[] { 12, 14, 17, 15, 19, 20, -11 }, 9);
}

/**
* * Given a number finds two numbers from an array so that the sum is equal
* to that number k.
*/
public static void printPairsUsingTwoPointers(int[] numbers, int k) {
if (numbers.length < 2) {
return;
}
Arrays.sort(numbers);
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == k) {
System.out.printf("(%d, %d) %n", numbers[left], numbers[right]);
left = left + 1;
right = right - 1;
} else if (sum < k) {
left = left + 1;
} else if (sum > k) {
right = right - 1;
}
}
}

/**
 * Utility method to print two elements in an array that sum to k
 * @param random
 * @param k
 */
public static void prettyPrint(int[] random, int k) {
System.out.println("input int array : " + Arrays.toString(random));
System.out
.println("All pairs in an array of integers whose sum is equal to a given value "
+ k);
printPairsUsingTwoPointers(random, k);
}
}

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.