-2
\$\begingroup\$

Input is a sorted array and a target sum. Find all sets of 3 unique elements that sum to a target.

Looking for lowest order (big O).

A, B, C are the indexes on the sorted array. A < B < C

Move AB together across the array starting with B = A + 1. Do a binary search on C for an upper bound for that A. Then walk B and C to the middle to test all possibilities for that A.

In theory worse case is O(n * n) but in practice it approaches $(n log n) because it bounds C using binary search for each A. Then it walks B and C to the middle so it avoids testing every B, C combination. And for each A it first checks if it is even possible which is the case quite often.

//test
List<int> rrr = Sum3(Enumerable.Range(0, 100).ToArray(), 150);
//end test

public static List<int> Sum3 (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
    //a++ b=a+1

    if (input.Length < 3)
        throw new ArgumentOutOfRangeException();
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Length - 1] + input[input.Length - 2] + input[input.Length - 3] < sum)
        throw new ArgumentOutOfRangeException();

    Array.Sort(input);
    List<int> result = new List<int>();
    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;

    while (true)  
    {
        a++;
        if (a == input.Length - 2)
            break;
        b = a + 1;
        if (input[a] + input[b] + input[b + 1] > sum)
            break;

        c = BinarySearch(input, sum - input[a] - input[b], b + 1, null);

        while(c > b)
        {
            currentSum = input[a] + input[b] + input[c];
            if (currentSum == sum)
            {
                result.Add(a);
                result.Add(b);
                result.Add(c);
                return result;
            }
            else if (currentSum < sum)
                b++;
            else
                c--;
        }
    }
    return null;
}

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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Given how the current answer may or may not have misinterpreted your question, it could be wise to expand your question a bit. "Find 3 elements to sum to a target." is awfully brief. \$\endgroup\$ – Mast Jun 17 '17 at 19:18
  • \$\begingroup\$ @Mast I don't know how to be more clear than 3 elements to sum to a target. What is ambiguous? Brief can be complete. \$\endgroup\$ – paparazzo Jun 17 '17 at 19:24
4
\$\begingroup\$
  • Inputting Sum3(int[] {3, 1, 1, 1, 0}, 3) errors. This is as you assume the array to be sorted, before sorting it.
  • You throw the same error when the array is not large enough, and when the input is invalid. You didn't even add a string to say what the error was, so this is just cryptic at best.
  • Coming from Python I like to keep functions to either mutating data, or not mutating it. This function should probably expect a sorted array as input, so it only has one responsibly. If you wish to take a non-sorted array, I'd deep clone the array, so that you don't affect usage elsewhere.
  • Defining result outside your while loop is confusing at best, do you use it anywhere other than when you return it? No? Then move it to where it's used.

    You can then combine all your result.Add's to then get:

    return new List<int> {a, b, c};
    

    This clearly shows the result is either null or just contains three numbers.

  • I personally don't like your lack of braces on some of your ifs.

    If I want to add to that if, I'd have to make the braces. It's a trivial task, but my IDE freezes, as I have to make a ton of syntax errors when adding either of the braces.

    It prevents me from writing buggy code, as I then don't have to worry if I write two lines of code after the if or not.

    This comes all at the cost of pressing one button, in most IDEs, when you made the if. A price I think is worth.

\$\endgroup\$
  • \$\begingroup\$ Good feedback, fair enough, +1 \$\endgroup\$ – paparazzo Jun 17 '17 at 19:58
  • \$\begingroup\$ I like the flow of no { } but at work I always use them \$\endgroup\$ – paparazzo Jun 18 '17 at 19:58
3
\$\begingroup\$

Your code seems quite complicated.

First of all, the outer while loop is not a while loop. It's a for loop:
for (int a = 0; a < input.Length - 2; a++) .... This way, the intent is clearer.

The logic of your code is also pretty hard to follow. You binary search for some position, then you move b and c left or right. I can't figure out what's going on. I'm not sure if the code is correct. Names like a, b, c don't help either. They are some indices, but what do they really mean? I have no idea. And why do you even use binary search? The inner while works in O(n) in the worst case, anyway.

I suggest using a more clear implementation. Here's my pseudocode:

for mid = 1..(input.length - 2)
    high = mid + 1
    for low = (mid - 1)..0
        while high < input.length and input[low] + input[mid] + input[high] < sum:
            high += 1
        if high < input.length and input[low] + input[mid] + input[high] == sum:
            return [low, mid, high]
return []

This way the meaning of the indices is clear. It's also clear why high should move right while low is moving left. There's no need to handle any corner cases.

I also suggest returning an empty list or null if the target sum is not found. I don't think that throwing exception is reasonable. Not finding the sum is a normal, not an exceptional situation.

\$\endgroup\$
  • \$\begingroup\$ First comment //a,b,c are index to input. Sorry you don't follow the algorithm. \$\endgroup\$ – paparazzo Jun 17 '17 at 18:55
  • \$\begingroup\$ @Paparazzi I understand that they're indices. It's not clear what exactly they stand for. \$\endgroup\$ – kraskevich Jun 17 '17 at 19:00
  • \$\begingroup\$ Have you tested if your suggestion works? Not found and not possible are not the same. \$\endgroup\$ – paparazzo Jun 17 '17 at 19:16
  • \$\begingroup\$ @Paparazzi I don't see any difference. Such a triplet either exists or it doesn't. I don't see the point in creating corner cases artificially. \$\endgroup\$ – kraskevich Jun 17 '17 at 19:31
  • \$\begingroup\$ OK you don't see the point. That is not creating a corner case. Again have you tested your code. I don't even know where it goes to test it. \$\endgroup\$ – paparazzo Jun 17 '17 at 19:34
0
\$\begingroup\$

I am not going to accept my own answer but this is how it currently looks

public static List<int> Sum3 (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.Length < 3)
        throw new ArgumentOutOfRangeException();
    //Array.Sort(input);
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Length - 1] + input[input.Length - 2] + input[input.Length - 3] < sum)
        throw new ArgumentOutOfRangeException();

    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;
    for (a = 0; a < input.Length - 2; a++)
    {
        if (input[a] + input[input.Length - 1] + input[input.Length - 2] < sum)
            continue;

        b = a + 1;
        if (input[a] + input[b] + input[b + 1] > sum)
            break;
        c = BinarySearch(input, sum - input[a] - input[b], b + 1, null);
        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\$

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.