Finding a number that is sum of two other numbers in a sorted array

Question

As it said in the topic, I have to check if there is a number that is the sum of two other numbers in a sorted array.

In first part of the question (for a unsorted array) I wrote a solution, just doing 3 loops and checking all the combinations.

Now, I can't understand how to build the most efficient algorithm to do the same, but with a sorted array.

Numbers are of type int (negative or positive) and any number can appear more then once.

Can somebody give a clue about that logic problem ?

Answer 1

None of the solutions given solve the question asked. The question asks to find a number inside the array that equals the sum of two other numbers in the same array. We aren't given a target sum beforehand. We're just given an array.

I've come up with a solution that runs in O(n²) running time and O(1) space complexity in the best case, and O(n) space complexity in the worst case (depending on the sort):

def hasSumOfTwoOthers(nums):
    nums.sort()
    for i in range(len(nums)):
        left, right = 0, i - 1
        while left < right:
            s = nums[left] + nums[right]
            if s == nums[i]:
                return True
            if s < nums[i]:
                left += 1
            else:
                right -= 1
    return False

This yields the following results:

ans = hasSumOfTwoOthers([1,3,2,5,3,6])
# Returns True

ans = hasSumOfTwoOthers([1,5,3,5,9,7])
# Returns False

Answer 2

An efficient way to do this would be using sorting and then a binary search.

Suppose the two numbers are x and y, x+y=SUM

For each x, search the array for the element SUM-x

Sort the array using mergesort.

Then for each element a[i] in the array a, do a binary search for the element (SUM-x) This algorithm should work in O(nlgn).

Here, binaryseacrh returns index of the search key if found, else it returns -1. SIZE is the arraysize

    for(int i=0;i<SIZE;i++)
      {
        int ind=binarysearch(SUM-a[i]);

        if(ind>0)
          printf("sum=%d + %d\n a[%d] + a[%d]\n"
                    ,a[i],a[ind],i,ind);
      }

Answer 3

This one is using Hash Set in Java; It is O(n) complexity.

public static void findPair3ProPrint(int[] array, int sum) {
    Set<Integer> hs = new HashSet<Integer>();       
    for (int i : array) {           
        if (hs.contains(sum-i)) {
            System.out.print("(" + i + ", " + (sum-i) + ")" + " ");
        }else{
            hs.add(i);  
        }   
    }
}

Answer 4

Here I am doing it using C:

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.

METHOD 1 (Use Sorting)

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum) 1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return 0

Example: Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array A = {-8, 1, 4, 6, 10, 45}

Initialize l = 0, r = 5

A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10

A[l] + A[r] ( -8 + 10) < 2 => increment l. Now l = 1

A[l] + A[r] ( 1 + 10) < 16 => increment l. Now l = 2

A[l] + A[r] ( 4 + 10) < 14 => increment l. Now l = 3

A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Implementation:

# include <stdio.h>
# define bool int

void quickSort(int *, int, int);

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
    int l, r;

    /* Sort the elements */
    quickSort(A, 0, arr_size-1);

    /* Now look for the two candidates in the sorted 
       array*/
    l = 0;
    r = arr_size-1; 
    while(l < r)
    {
         if(A[l] + A[r] == sum)
              return 1; 
         else if(A[l] + A[r] < sum)
              l++;
         else // A[i] + A[j] > sum
              r--;
    }    
    return 0;
}

/* Driver program to test above function */
int main()
{
    int A[] = {1, 4, 45, 6, 10, -8};
    int n = 16;
    int arr_size = 6;

    if( hasArrayTwoCandidates(A, arr_size, n))
        printf("Array has two elements with sum 16");
    else
        printf("Array doesn't have two elements with sum 16 ");

    getchar();
    return 0;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING 
    PURPOSE */
void exchange(int *a, int *b)
{
    int temp;
    temp = *a;
    *a   = *b;
    *b   = temp;
}

int partition(int A[], int si, int ei)
{
    int x = A[ei];
    int i = (si - 1);
    int j;

    for (j = si; j <= ei - 1; j++)
    {
        if(A[j] <= x)
        {
            i++;
            exchange(&A[i], &A[j]);
        }
    }
    exchange (&A[i + 1], &A[ei]);
    return (i + 1);
}

/* Implementation of Quick Sort
A[] --> Array to be sorted
si  --> Starting index
ei  --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
    int pi;    /* Partitioning index */
    if(si < ei)
    {
        pi = partition(A, si, ei);
        quickSort(A, si, pi - 1);
        quickSort(A, pi + 1, ei);
    }
}