-1
$\begingroup$

Given a sorted array of $n$ integers ,and some other integer $m$, find the $3$ numbers in the array $x,y,z$ such that $x+y+z\ge m$,and their sum is minimal.

If there are no such,return null.

Any ideas for an efficient algorithm to find it?

$\endgroup$
  • 3
    $\begingroup$ Do you have any ideas? What have you tried? Can you think of any algorithms at all? Did you try solving the variant with only two variables $x,y$? $\endgroup$ – Yuval Filmus Apr 25 '17 at 20:30
  • $\begingroup$ Note that this problem is at least as hard as 3SUM (why?), if by "smallest 3 numbers" you mean that you want to minimize $x+y+z$ under the constraint $x+y+z \ge m$. $\endgroup$ – Yuval Filmus Apr 25 '17 at 20:31
  • $\begingroup$ Obviously possible in $O(n^2)$ with any reasonable definition of "smallest 3 numbers". Possibly faster depending on definition of "smallest 3 numbers". $\endgroup$ – gnasher729 Apr 25 '17 at 20:39
  • $\begingroup$ @YuvalFilmus It's not a HW question or such.I'm trying to implement some other algorithm,which I need to find those 3 numbers for that algorithm.I don't know how to do it.And yes,that's what I meant by smallest. $\endgroup$ – ChikChak Apr 25 '17 at 20:46
  • $\begingroup$ It still seems unclear. Consider this array [1,2,3,4,5] and m=8. How do you want to compare [1,2,5] and [1,3,4]. Do you need all of them or just one of them will do the job? $\endgroup$ – Prateek Apr 25 '17 at 20:57
2
$\begingroup$

The algorithm for finding three number $x, y, z$ under the constraint $x+y+z \ge m $ can be extended from the idea of finding two numbers $x, y$ under a similar constraint $x+y \ge m $.

Initially we fix the value of $x = A_1$, first element of array. Next we will look for $y$ and $z$ in the subarray $A_2 ... A_n$. We repeat the above step by setting $x = A_2$ in the next iteration and look for $y$ and $z$ in the subarray $A_3 ... A_n$. We repeat this step until one of the following conditions are meet.

  1. We find a triple $x, y, z$ such that $x + y + z = m$. As that is the minimum we have to look for, and you just need one of them.
  2. We reach a point where we have set $x = A_{n-2}$ and looked for other two values in the second last and last element of the array i.e., the triple $<A_{n-2}, A_{n-1}, A_{n}>$

Also, there could be many triples in an array satisfying the condition $x+y+z \ge m$ and we need the one with the minimum sum. For this, we keep a separate copy of triple found so far under the specified condition and compare it everytime we find a new one.

Here is the pseudocode

FindTriple(A,n,m)
    if A[n-2]+A[n-1]+A[n] < m
        print "No solution"
        return 0

    #Set to some maximum value, for first time comparison
    x = y = z = INFINITY

    for i = 1 to n
        j = i+1
        k = n

        while k>j
            sum = A[i]+A[j]+A[k]

            if sum == m
                print <A[i],A[j],A[k]>
                return 1
            else if sum > m
                if sum < (x+y+z)
                    <x,y,z> = <A[i],A[j],A[k]>
                k=k-1
            else j = j+1

    print <x,y,z>

Runtime complexity of this algorithm is $O(n^2)$.

I took time answering this question because I was looking for an algorithm with better runtime complexity. Thanks to Yuval Filmus's answer that saved a lot of my time.


Here is the link to the working implementation of this algorithm in C language

$\endgroup$
  • $\begingroup$ I think there is a typo in the first line of code in findTriple(). The middle term of the first expression in the if statement should be a[n-1]. $\endgroup$ – Rich Holton Apr 27 '17 at 0:50
  • $\begingroup$ @RichHolton Thank you for pointing that out. I have fixed it. $\endgroup$ – Prateek Apr 27 '17 at 4:36
2
$\begingroup$

You can solve this in $O(n^2\log n)$ in the following way:

  1. Construct and sort the list consisting of all sums $x + y$.
  2. Go over all $z$, and for each them find the minimal $x+y \geq m-z$ using binary search.

It is very likely that this can be improved to $O(n^2)$ by adapting the 3SUM quadratic algorithm.

On the other hand, you can clearly solve 3SUM given a solution to your problem (just check whether $x+y+z=m$), making it 3SUM-hard to improve $O(n^2)$ to $O(n^{2-\epsilon})$ for any $\epsilon > 0$. (That is, the 3SUM conjecture implies that no $O(n^{2-\epsilon})$ algorithms exist.)

$\endgroup$
  • $\begingroup$ How can I modify the quadratic algorithm to work in this case aswell? The problem with it that this algorithm looks only for 3 numbers so thier sum will be exactly , when I allow it to be "a bit" more as well.. $\endgroup$ – ChikChak Apr 25 '17 at 21:26
  • $\begingroup$ Unfortunately I am not willing to answer this question. You'll have to figure out the required modification (if it is at all possible) on your own. $\endgroup$ – Yuval Filmus Apr 25 '17 at 21:29
  • $\begingroup$ But is it even possible? $\endgroup$ – ChikChak Apr 25 '17 at 21:35
  • $\begingroup$ I don't know, but it seems likely. $\endgroup$ – Yuval Filmus Apr 25 '17 at 22:03
-2
$\begingroup$

Not getting the down votes so I wrote a program to test.

a, b, c are the indexes
a < b < c

m is target

Where this differs from the accepted solution is for each a, a+1 it does a binary search for the c rather than walk it down. And it gives up if a + the last two (biggest) are < sum. This shifts it towards $O(n log n)$ but worst case it is still $O(n * n)$.

  1. a = 0, b = 1
  2. perform a binary search on c
  3. if sum = m then done
  4. if sum > target then c-- else b++
  5. if a == m.length - 2 done solution not found
  6. if c == b then a++ b=a+1 go to 2
  7. goto 3

I think this is close to $O(n log n)$

public static int BinarySearch(int[] A, int T, int? l, int? r)
{
    // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
    // 1. Set L to 0 and R to n − 1.
    // 2. If L > R, the search terminates as unsuccessful.
    // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
    // 4. If Am < T, set L to m + 1 and go to step 2.
    // 5. If Am > T, set R to m – 1 and go to step 2.
    // 6. Now Am = T, the search is done; return m.
    Array.Sort(A);
    int M = -1;
    int L = l == null ? 0            : (int)l;
    int R = r == null ? A.Length - 1 : (int)r;
    while (L <= R)
    {
        M = (L + R) / 2;
        if (A[M] < T) L = M + 1;
        else if (A[M] > T) R = M - 1;
        else return M;
    }
    return M;
}
public static int BinarySearchList(List<int> A, int T, int? l, int? r)
{
    // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
    // 1. Set L to 0 and R to n − 1.
    // 2. If L > R, the search terminates as unsuccessful.
    // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
    // 4. If Am < T, set L to m + 1 and go to step 2.
    // 5. If Am > T, set R to m – 1 and go to step 2.
    // 6. Now Am = T, the search is done; return m.

    int M = -1;
    int L = l == null ? 0 : (int)l;
    int R = r == null ? A.Count() - 1 : (int)r;
    while (L <= R)
    {
        M = (L + R) / 2;
        if (A[M] < T) L = M + 1;
        else if (A[M] > T) R = M - 1;
        else return M;
    }
    return M;
}
public static List<int> Sum3(List<int> input, int sum)
{
    //a,b,c are index to input
    //start a = 0, b = 1 and solve for c
    //add b until over 
    //reduce c until under
    //when b=c the a++ b=a+1

    if (input.Count() < 3)
        throw new ArgumentOutOfRangeException();
    //is it sorted
    int? iLast = null;
    for (int i = 0; i < input.Count(); i++)
    {
        if (iLast != null && i <= iLast)
            throw new ArgumentOutOfRangeException();
        iLast = i;
    }
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Count() - 1] + input[input.Count() - 2] + input[input.Count() - 3] < sum)
        throw new ArgumentOutOfRangeException();

    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;
    int? lastC = null;
    int count = 0;
    for (a = 0; a < input.Count() - 2; a++)
    {
        count++;
        if (input[a] + input[input.Count() - 1] + input[input.Count() - 2] < sum)
            continue;
        if (input[a] + input[a + 1] + input[a + 2] > sum)
            break;
        b = a + 1;              
        c = BinarySearchList(input, sum - input[a] - input[b], b + 1, lastC);
        lastC = c;
        while(c > b)
        {
            currentSum = input[a] + input[b] + input[c];
            if (currentSum == sum)
                return new List<int> { a, b, c };
            if (currentSum < sum)
                b++;
            else
                c--;
        }
    }
    return null;
}
$\endgroup$
  • 1
    $\begingroup$ Care to explain why it works and why you think it's $O(n\log n)$? As I'm pretty sure we've said to you before, we're looking for full answers, not just (pseudo-)code dumps. $\endgroup$ – David Richerby Apr 26 '17 at 20:29
  • $\begingroup$ @DavidRicherby You make n moves and one log lookup for each move. Actually worse case (n-2) log((n-2)/2) $\endgroup$ – paparazzo Apr 26 '17 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.