Write a C program that, given an array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.Suppose are array is
2, 5, 20, 50, 85, 90
And our asnwer is 70, so output should be= 20, 50
Variation 1: Pair with given sum in sorted and rotated array
Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum ‘x’. It may be assumed that all elements in array are distinct.
Questions 2: Triplets in an array with sum 0
Given an array of n integers, find an algorithm to find triplets in the array such that sum of the three numbers is zero.
What is the order of your algorithm?
Strategy:
This is also known as the 3sum problem. The 3sum problem is the extension of the problem below:
Given a set S of n integers, find all pairs of integers of a and b in S such that a + b = k?
The above problem can be solved in O(n) time, assuming that the set S is already sorted. By using two index first and last, each pointing to the first and last element, we look at the element pointed by first, which we call A. We know that we need to find B = k – A, the complement of A. If the element pointed by last is less than B, we know that the choice is to increment pointer first by one step. Similarly, if the element pointed by last is greater than B, we decrement pointer last by one step. We are progressively refining the sum step by step. Since each step we move a pointer one step, there are at most n steps, which gives the complexity of O(n).
By incorporating the solution above, we can solve the 3sum problem in O(n^2) time, which is a straight forward extension.
set<vector<int> > find_triplets(vector<int> arr) {
sort(arr.begin(), arr.end());
set<vector<int> > triplets;
vector<int> triplet(3);
int n = arr.size();
for (int i = 0;i < n; i++) {
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum_two = arr[i] + arr[j];
if (sum_two + arr[k] < 0) {
j++;
} else if (sum_two + arr[k] > 0) {
k--;
} else {
triplet[0] = arr[i];
triplet[1] = arr[j];
triplet[2] = arr[k];
triplets.insert(triplet);
j++;
k--;
}
}
}
return triplets;
}
Note that a set is chosen to store the triplets, because we are only interested in unique triplets. Since the set S is already sorted, and we don’t look back as it progresses forward, we can guarantee there will be no duplicate triplets (Even though the set might have duplicate elements.
Question 3: Pythagorean Triplet in an array
Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2.
Example:
Input: arr[] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).
Input: arr[] = {10, 4, 6, 12, 5}
Output: False
There is no Pythagorean triplet.
Question 4: Maximum product of a triplet in array
Given an integer array, find a maximum product of a triplet in array.
Question 5: Triplets with Geometric Progression
Given a sorted array of distinct positive integers, print all triplets that forms Geometric Progression with integral common ratio.
http://www.geeksforgeeks.org/find-all-triplets-in-a-sorted-array-that-forms-geometric-progression/
