InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Determine whether there is a triplet in the array whose total equals the given value, given an array and a value. If a triplet of this type exists in the array, print it and return true. If not, return false. |
|
Answer» Example: Input: arr = {12, 3, 4, 1, 6, 9}, sum = 24;Output: 12, 3, 9Explanation: The array contains a triplet (12, 3 and 9) whose sum is 24. Input: arr = {1, 2, 3, 4, 5}, sum = 9Output: 5, 3, 1Explanation: There is a triplet (5, 3 and 1) present in the array whose sum is 9. Approach: The algorithm's performance can be increased by sorting the array. The two-pointer technique is USED in this effective method. Fix the first element of the triplet by traversing the array. Find if there is a pair whose TOTAL equals x – array[i] using the Two Pointers technique. Because the two pointers approach takes linear time, it is preferable to a nested loop. Code: #include <bits/stdc++.h>using namespace std;// returns true if there is triplet with sum equal// to 'sum' present in arr[]. Also, prints the tripletbool findTriplet(int arr[], int arr_size, int sum){ int low, high; //sorting the entire array sort(arr, arr + arr_size); //Fixing the first element one by one and finding the other two elements for (int i = 0; i < arr_size - 2; i++) { // Start two index variables from opposite corners of the array and move them toward each other to find the other two MEMBERS. low = i + 1; // index of the first element in the remaining elements high = arr_size - 1; // index of the last element while (low < high) { if (arr[i] + arr[low] + arr[high] == sum) { printf("The triplet is %d, %d, %d", arr[i], arr[low], arr[high]); return true; } else if (arr[i] + arr[low] + arr[high] < sum) low++; else // arr[i] + arr[low] + arr[high] > sum high--; } } // If we reach here, then no triplet was found return FALSE;}int MAIN(){ int arr[] = { 12, 3, 4, 1, 6, 9 }; int sum = 24; int arr_size = sizeof(arr) / sizeof(arr[0]); findTriplet(arr, arr_size, sum); return 0;}Output: The triplet is 12, 3, 9Explanation: In the above code, the function findTriplet takes the input of an array, the size of the array and the sum required. First of all, we sort the array given. We traverse the array elements and fix the first element of the triplet in each iteration. We use a two-pointer approach and find the remaining two elements of the triplet, if it is possible with the given array. Useful Resources:
|
|