Given a sorted array, output all triplets <a,b,c> such that a-b = c

Given a sorted array, output all triplets such that a-b = c. The code I tried so far is as below; but there are following test cases-

-12 = -7 - 5
-12 =  3 - 15
 -7 = -4 - 3
 -7 =  3 - 10
 -7 =  9 - 16
 -4 =  5 - 9
  3 = -4 - -7
  5 = -7 - -12
  5 = 15 - 10 
 10 = 3 - -7 
 10 = 15 - 5
15 = 3 - (-12)
16 = 9 - (-7)

while my program prints only-

-12 = -7 - 5
 -7 = -4 - 3
 -12 = 3 - 15
 -7 = 3 - 10
 -4 = 5 - 9
 -7 = 9 - 16
 5 = 15 - 10

means only the abs difference! Any suggestion ll be great help!

void binder(int*a, int n) {
    int i;
  for (i = 0; i < n; i++) {
    int current = a[i];
    int left = 0;
    int right = n-1;
    while (left 开发者_如何学运维< right) {
      if ( left == i ) {
        left++;
        continue;
      }


if (right == i) {
        right--;
        continue;
      }



if (a[left] + a[right] < current) {
        left++;
      } else if (a[left] + a[right] > current) {
        right--;
      } else {
        printf("\n %d = %d - %d",a[left],current, a[right]);
        left++;
        right--;
      }
    }
  }
}



int main() {
  int a[] = {-12, -7, -4, 0, 3, 5, 9, 10, 15, 16};
  binder(a, 10);
  return 0;
}

It seems as though the test case is also missing a triplet:

9 =  5 - (-4)

Try changing your printing from:

printf("\n %d = %d - %d",a[left],current, a[right]);

to:

printf("\n %d = %d - %d",a[left],current, a[right]);
printf("\n %d = %d - %d",a[right],current, a[left]);

This solution is O(n^3), but it should work.

void binder(int*a, int n)
{
    for(int left = 0; left < n; left++)
    {
        for(int right = 0; right < n; right++)
        {
            for(int result = 0; result < n; result++)
            {
                if(left != right && left != result && result != right && a[left] - a[right] == a[result])
                    printf("\n %d = %d - %d", a[result], a[left], a[right]);
            }
        }
    }
}

How about something like this:

HashTable table;
for b = 0 to n-1:
    for c = 0 to n-1:
        table[b + c] = <b, c>
    end for
end for

for a = 0 to n-1:
    if table[a] exists and (<b, c> in table[a] where b != a and c != a) then:
        output <a, b, c>
    end if
end for

So, if we consider "a=b+c", for each (b, c) pair of values, we place that in a hash table, associating it with the (b, c) pair [O(n^2)].

Then, we go through the array again and if a value appears in the hash table, and the associated pairs are for different indices, then we've found a new entry (rearranging the terms back into "a-b=c"). This step is O(n), resulting in a O(n^2) solution overall.

I think we can see this question as a variation on the "find pairs of values in an array that sum up to S, for a fixed S" problem.

If they are sorted, (and as Hanning pointed out, a-b=c is the same as a=b+c) you can start with the smallest b and c, and add them, and this should lead to the smallest a. Now while increasing b or c, a can only get bigger too, so you should have never to look back.

If you make a table of b's and c's and their sum (which should be one of the a's):

c\ b:-12    3   4   5   7  10  15 16  
-12: -24, -19, -9, -7, -3, -2,  3, 4
 -7:  -9,  -4,  6,  8, 12, 13, 18, 
  3:  -8,  -3,  7,  9, 13, 14, 19, 
  5:  -7,  -2,  8, 10, 14, 15, 
  9:  -5,   0, 10, 12, 16, 
 10:  -2,   3, 13, 15,  
 15:   3,   8, 18,  
 16:   4,   9, 19,  

you see, that I omited the values on the lower right, because the previous value (from left) already exceeded the maximum a (15), so a higher value can't match.

Of course, for such a small number of equations, you waste much more time thinking about optimization, than you gain from omitting superfluous calculations. For much bigger sets of values, it might be useful, to optimize.

you have missed one more iteration/loop in your code. since you are using brute force strategy so analysis say that it will take O(n^3) space and you code's time complexity seems O(n^2). here is the case which will help you to understand. you check for : a = b-c and you skip the check for : c = b-a