I need an algorithm to determine if an array contains two elements that sum to a given integer.
The array is sorted.
The algorithm should be recursive and runs in O(n).
The recursive step should be based on the sum, meaning the method passes the sum and return true or false depending on the end result (if two elements are found - return true, else - return false)
Only linear data structures can be used.
Any ideas are appreciated..
You can convert any iterative algorithm into a recursive one by using (for instance) tail recursion. I'd be more expansive, if it weren't homework. I think you'll understand it from the other post.
Here is a solution witch takes into account duplicate entries. It is written in javascript and assumes array is sorted. The solution runs in O(n) time and does not use any extra memory aside from variable.
var count_pairs = function(_arr,x) {
if(!x) x = 0;
var pairs = 0;
var i = 0;
var k = _arr.length-1;
if((k+1)<2) return pairs;
var halfX = x/2;
while(i<k) {
var curK = _arr[k];
var curI = _arr[i];
var pairsThisLoop = 0;
if(curK+curI==x) {
// if midpoint and equal find combinations
if(curK==curI) {
var comb = 1;
while(--k>=i) pairs+=(comb++);
break;
}
// count pair and k duplicates
pairsThisLoop++;
while(_arr[--k]==curK) pairsThisLoop++;
// add k side pairs to running total for every i side pair found
pairs+=pairsThisLoop;
while(_arr[++i]==curI) pairs+=pairsThisLoop;
} else {
// if we are at a mid point
if(curK==curI) break;
var distK = Math.abs(halfX-curK);
var distI = Math.abs(halfX-curI);
if(distI > distK) while(_arr[++i]==curI);
else while(_arr[--k]==curK);
}
}
return pairs;
}
I solved this during an interview for a large corporation. They took it but not me. So here it is for everyone.
Start at both side of the array and slowly work your way inwards making sure to count duplicates if they exist.
It only counts pairs but can be reworked to
Enjoy!
It is pretty easy. It is important for array to be sorted.
Correct algorithm with O(n) time complexity and no additional space is:
public static boolean isContainsSum(int[] arr, int sum) {
for (int i = 0, j = arr.length - 1; i < j; ) {
if (arr[i] + arr[j] == sum)
return true;
if (arr[i] + arr[j] < sum)
i++;
else
j--;
}
return false;
}
To make it recursive, you need just replace i and j iterations with recursive call:
public static boolean isContainsSumRecursive(int[] arr, int sum) {
return isContainsSumRecursive(arr, sum, 0, arr.length - 1);
}
private static boolean isContainsSumRecursive(int[] arr, int sum, int i, int j) {
if (i == j)
return false;
if (arr[i] + arr[j] == sum)
return true;
if (arr[i] + arr[j] < sum)
return isContainsSumRecursive(arr, sum, i + 1, j);
return isContainsSumRecursive(arr, sum, i, j - 1);
}
Normally I'd use a Map, but since one of the requirements is to use a linear data structure, I think that's excluded, so I'd go about using a boolean array.
public boolean hasSum( int[] numbers, int target )
{
boolean[] hits = new boolean[ target + 1 ];
return hasSumRecursive( 0, numbers, target, hits );
}
public boolean hasSumRecursive( int index, int[] numbers, int target, boolean[] hits )
{
...
}
Hopefully this is a good enough hint.
I think hash is ok, for example, 1,3,7,9,12,14,33...
if we want sum=21, we hash the numbers into a hash table, So, O(n).
we iterator them, when we get 7, we let 21-7=14, so we hash 14, we can find it. so 7+14=21,
we got it!
Here is my solution: I iterate until the first number is greater than the expected sum, then until to second one or the sum of two is greater than the expected sum. If I do not want a correct answer, I return {-1,-1} (assuming all numbers are positive integers)
{
private static int[] sumOfTwo(int[] input, int k) {
for (int i = 0; i < input.length - 1; i++) {
int first = input[i];
for (int j = 1; j < input.length; j++) {
int second = input[j];
int sum = first + second;
if (sum == k) {
int[] result = {first, second};
return result;
}
if (second > k || sum > k) {
break;
}
}
if (first > k) {
break;
}
}
int[] begin = {-1, -1};
return begin;
}
}
Here is the recursion method to perform the groupSum
public boolean groupSum(int start, int[] nums, int target)
{
if (start >= nums.length) {
return (target == 0);
}
return groupSum(start + 1, nums, target - nums[start]) || groupSum(start +
1,nums,target)
}
Here is my solution using recursion
pair<int,int> twoSum(int arr[], int s, int e, int target, pair<int, int>p){
//base case
if(arr[s] + arr[e] == target){
// pair<int,int>p;
p.first = arr[s];
p.second = arr[e];
return p;
}
while(s < e-1){
if(arr[s] + arr[e] < target){
s++;
return twoSum(arr, s, e, target, p);
}
if(arr[s] + arr[e] > target){
e--;
return twoSum(arr, s, e, target, p);
}
}
//if there is no pair possible
cout<<"pair is not possible" <<endl;
return p;
}
def ExistsSum(A, i, j, Target):
if i >= j:
return False # Failure, all candidate pairs exhausted
if A[i] + A[j] < Target:
return ExistsSum(A, i+1, j, Target) # Try a larger sum
if A[i] + A[j] > Target:
return ExistsSum(A, i, j-1, Target) # Try a smaller sum
return True # Success
Run with
ExistsSum(A, 0, len(A)-1, Target)
bool solve(vector<int> &sorted_array, int l, int r, int target) {
if(l>=r) {
return false;
}
if(sorted_array[l] + sorted_array[r] == target) {
return true;
}
if(sorted_array[l] + sorted_array[r] > target) {
return solve(sorted_array, l, r-1, target);
}
if(sorted_array[l] + sorted_array[r] < target) {
return solve(sorted_array, l+1, r, target);
}
}
int main() {
vector<int> a = ...
solve(a, 0, a.size() - 1, target)
}
Sort the array. Search for the complement of each number (sum-number). Complexity O(nlogn).
