You have been given a random integer array/list(ARR) and a number X. Find and return the number of distinct triplet(s) in the array/list which sum to X.

I have written this code:

public class Solution { 
public static void merge(int arr[], int lb, int mid, int ub){
    int n1 = mid - lb   1;
    int n2 = ub - mid;

    int arr1[] = new int[n1];
    int arr2[] = new int[n2];

    for (int i = 0; i < n1; i  )
        arr1[i] = arr[lb   i];
    for (int j = 0; j < n2; j  )
        arr2[j] = arr[mid   1   j];


    int i = 0, j = 0;

    int k = lb;
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[k] = arr1[i];
            i  ;
        }
        else {
            arr[k] = arr2[j];
            j  ;
        }
        k  ;
    }

    while (i < n1) {
        arr[k] = arr1[i];
        i  ;
        k  ;
    }

    while (j < n2) {
        arr[k] = arr2[j];
        j  ;
        k  ;
    }
}


public static void mergeSort(int arr[], int lb, int ub){
    if (lb < ub) {
        int mid = lb   (ub - lb) / 2;

        mergeSort(arr, lb, mid);
        mergeSort(arr, mid   1, ub);
        merge(arr, lb, mid, ub);
    }
}

public static int tripletSum(int[] arr, int num) {
    //Your code goes here
    mergeSort(arr, 0, arr.length-1); 
    int n = arr.length;
    int count = 0;
    
    for (int i = 0; i < n - 2; i  ){
        int sum = num - arr[i];
        
        int j = i 1;
        int k = n-1;
        
        while (j<k)
        {
            if(arr[j] arr[k] == sum){
                count  ;
                k--;
            }
            else if(arr[j] arr[k]>sum){
                k--;
            }
            else{
                j  ;
            }
        }
    }    
    return count;
}

}

Input array was - 1 3 3 3 3 3 3 Input num = 9 Output Generated - 10 Expected output - 20

Help me out with this I'm trying to find the solution for many hours. Also, the time complexity of the program should not exceed O(n^2).

CodePudding user response：

I did it in this way, hope I understood it well.

public static int tripletSum(int[] arr, int num) {
    int loops = 0; // just to check the quality of the code
    int counter = 0;
    for (int i1 = 0; i1 < arr.length - 2; i1  ) {
        for (int i2 = i1   1; i2 < arr.length - 1; i2  ) {
            for (int i3 = i2   1; i3 < arr.length; i3  ) {
                loops  ;
                if (arr[i1]   arr[i2]   arr[i3] == num) {
                    counter  ;
                }
            }
        }
    }
    // Check for not exceeding O(n^2)
    if (loops <= arr.length * arr.length) {
        System.io.println("Well done");
    } else {
        System.io.println("Too many cycles");
    }
    return counter;
}

I iterate from "left" to "right" over the array and walking more and more to the "right".

1st, 2nd, 3rd
1st, 2nd, 4th
...
1st, 2nd, nth
2nd, 3rd, 4th
2nd, 3rd, 5th
...
2nd, 3rd, nth
.
.
.
nth - 2, nth - 1, nth

I iterated 35 times, but could iterate 7^2 = 49 times --> "Well done"

CodePudding user response：

You missed one loop. The fixed code:

    public static int tripletSum(int[] arr, int num) {
    //Your code goes here
    mergeSort(arr, 0, arr.length - 1);
    int n = arr.length;
    int count = 0;

    for (int i = 0; i < n - 2; i  ) {
        int sum = num - arr[i];
        
        for (int j = i 1; j < n-1; j  ) {
            int k = n-1;
            while (j < k) {
                if (arr[j]   arr[k] == sum) {
                    count  ;
                    k--;
                } else if (arr[j]   arr[k] > sum) {
                    k--;
                } else {
                    j  ;
                }
            }
        }
    }
    return count;
}

CodePudding user response：

OK, then optimized version:

public static int tripletSum(int[] arr, int num) {
    //Your code goes here
    mergeSort(arr, 0, arr.length - 1);
    int n = arr.length;
    int count = 0;
    for (int i = 0; i < n - 2; i  ) {
        int sum = num - arr[i];

        int maxK = n - 1;
        for (int j = i   1; j < n - 1; j  ) {
            int k = maxK;

            while (j < k) {
                if (arr[j]   arr[k] == sum) {
                    count  ;
                    k--;
                } else if (arr[j]   arr[k] > sum) {
                    k--;
                    maxK--;
                } else {
                    j  ;
                }
            }
        }
    }
    return count;
}