0 votes
60 views
in Data Structure And Algorithm by (3.7k points)
Find a triplet in unsorted array that sum to a given value in java ?

int arr[] = {12, 3, 4, 1, 6, 9};
int sum = 24;

3 Answers

0 votes
by (3.7k points)

See the very simple solution comes in our mind. We have three loops and see the sum of given triplet is equal to given sum.

public static void main(String[] args) {
        int arr[] = {12, 3, 4, 1, 6, 9};
        int sum = 24;
        boolean isFound = isTripletInUnSortedArray(arr,sum);
        System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");       
    }

//Time Complexity : O(n^3)
    private static boolean isTripletInUnSortedArray(int[] arr, int sum) {
        //Base check
        if(arr.length < 3)
            return false;
        for(int i=0; i<arr.length; i++) {
            for(int j=i+1; j<arr.length; j++) {
                for(int k=j+1; k<arr.length; k++) {
                    if(arr[i]+arr[j]+arr[k] == sum) {
                        System.out.println("Triplet: " + arr[i] + ", " + arr[j] + ", " + arr[k]);
                        return true;
                    }
                }
            }
        }
        System.out.println("Triplet is not found");
        return false;
    }

Output:-

Triplet: 12, 3, 9
Pair Found

0 votes
by (2.8k points)

See the given solution to find triplet in unsorted array. This solution is nice by using hashing in term of time complexity. This solution will take O(n^2) time complexity and O(n)  space complexity.

See the running code to find triplet in unsorted array.:-

public static void main(String[] args) {

int arr[] = {12, 3, 4, 1, 6, 9};

int sum = 24;

isFound = isTripletInUnSortedArrayUsingHashing(arr,sum);

System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");

}

 //Time Complexity:- O(n^2)

//Space Complexity:- O(n)

private static boolean isTripletInUnSortedArrayUsingHashing(int[] arr, int sum) {

// Fix the first element as arr[i] 

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

            // Find pair in subarray A[i+1..n-1] 

            // with sum equal to sum - A[i] 

            Set<Integer> set = new HashSet<Integer>(); 

            int curr_sum = sum - arr[i]; 

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

                if (set.contains(curr_sum - arr[j]) ) { 

                    System.out.println("Triplet is ["+ arr[i]+", "+ arr[j]+", "+ (curr_sum - arr[j])+"]"); 

                    return true; 

                } 

                set.add(arr[j]); 

            } 

        }

return false;

}

0 votes
by (3.9k points)

This solution will take only O(n^2) time complexity. In this solution, first of all sort the array and find triplet in sorted array.

See the running code to find the triplet in unsorted array:-

public static void main(String[] args) {

int arr[] = {12, 3, 4, 1, 6, 9};

int sum = 24;

isFound = isTripletInUnSortedArrayUsingSorting(arr,sum);

System.out.println(isFound == true ? "Pair Found" : "Pair Not Found");

}

//If arry not sorted then first of all sort the array O(n log n) and find the pairs. Unsorted array Time Complexity O(n log n)+O(n^2).

//Don't use hashing because hashing will require O(n)extra space. So, bellow approach is better 

//Time Complexity O(n^2)

private static boolean isTripletInUnSortedArrayUsingSorting(int[] arr, int sum) {

/* Sort the elements */

        quickSort(arr, 0, arr.length - 1);

//Base check

if(arr.length < 3)

return false;

int len = arr.length;

//O(n)

for(int i=0; i<len; i++) {

//O(n)

if(isPair(arr, i+1, len-1, sum-arr[i])) {

System.out.println(arr[i]+"]");

return true;

}

}

return false;

}

//Time Complexity O(n)

private static boolean isPair(int[] arr, int left, int right, int sum) {

int start=left, end=right;

while(start<end) {

if(arr[start]+arr[end]==sum) {

System.out.print("Pair: ["+arr[start]+", "+ arr[end]+", ");

return true;

}

if(arr[start]+arr[end] > sum) {

end--;

}else {

start++;

}

}

return false;

}

//Time Complexity O(n log n)

//start:- Starting index 

    //end:- Ending index 

private static void quickSort(int arr[], int start, int end) { 

        int pi; 

  

        /* Partitioning index */

        if (start < end) { 

            pi = partition(arr, start, end); 

            quickSort(arr, start, pi - 1); 

            quickSort(arr, pi + 1, end); 

        } 

    } 

private static int partition(int arr[], int start, int end) { 

        int x = arr[end]; 

        int i = (start - 1); 

        int j; 

  

        for (j = start; j <= end - 1; j++) { 

            if (arr[j] <= x) { 

                i++; 

                int temp = arr[i]; 

                arr[i] = arr[j]; 

                arr[j] = temp; 

            } 

        } 

        int temp = arr[i + 1]; 

        arr[i + 1] = arr[end]; 

        arr[end] = temp; 

        return (i + 1); 

    } 

Output:-

Pair: [9, 12, 3]

Pair Found

Share:- Whatsapp Facebook Facebook


Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

...