CODEWITHSUNDEEP
javaarraysalgorithm
Dilee
Dilee

Reputation: 276

K-complementary pairs using given array of integers effectively

I am very new to programming. I need to find the K-complementary pairs using given array of integers effectively. I have written the below code. It includes the duplication. I need to eliminate that duplication. So please help me to remove that duplication and please suggest if there is a better efficient way to do it. 

public class KComplexityOfArray {


public static StringBuffer oldFunction(int arr[], int k) {
    int result = 0;
    StringBuffer sb = new StringBuffer();

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            if (i != j && arr[i] + arr[j] == k) {
                sb.append(arr[i] + "," + arr[j]);
                result++;
            }
        }
    }
    System.out.println(result);
    return sb;
}



public static void main(String[] args) {
    int[] intArray1 = new int[]{4, 5, 6, 3, 1, 8, -7, -6, 7};
    int[] intArray2 = new int[]{1, 2, 7, 5, 6, 3};
    int[] intArray = new int[]{4, 5, 6, 3, 1, 8, -7, -6};
    int k = 9;
    System.out.println("No of k complementary pairs : " + oldFunction(intArray2, k));
}

}

Please anybody help me to sort this out. Thanks

Upvotes: 2

Views: 2576

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13994

This code is wrong, considering two different elements constitute a pair:

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {

Instead you should do j=i+1:

for (int i = 0; i < arr.length; i++) {
    for (int j = i+1; j < arr.length; j++) {

please suggest if there is a better efficient way to do it.

Your solution has TC of O(N^2). Instead you can reduce it in O(NlogN). See how:

  1. Sort the array.
  2. Use two index positions, i and j set to 0 and N-1 resp.
  3. Now, if the sum of a[i] and a[j] equals k, print it. Else if sum < K, advance i by 1, else reduce j by 1.
  4. Repeat Step 3 till (i < j)

Step 1 takes O(NlogN) and remaining steps take O(N); combining both incurs O(NLogN)

Upvotes: 2

SlumpA
SlumpA

Reputation: 904

If I understand correctly your problem, you should replace

for (int j = 0; j < arr.length; j++) {

with

for (int j = i+1; j < arr.length; j++) {

Upvotes: 0

Related Questions