0
$\begingroup$

So I have an array sized N. It is sure that array has all distinct elements.

I need to find sum of all possible triplets in that array and for that i need to find all possible triplets.

What i did: looping through array with three nested $for$ loops but that gives O(n^3).

I want to optimise the algorithm as n is very large(upto 10000)

Eg: Array==> {1,2,3,4,5}

Possible triplets: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ What do you mean by "sum of all possible triplets"? The sum of the elements in each triplet over all triplets? $\endgroup$
    – quicksort
    Commented Jan 21, 2017 at 15:19
  • $\begingroup$ @quicksort Yes.. $\endgroup$
    – Ayush Goyal
    Commented Jan 21, 2017 at 15:58
  • 1
    $\begingroup$ The beginners mistake: You found an obvious way to get the result, and there is a step in that obvious method taking O (n^3). You try to find a way to do that part faster, instead of stepping back and realising that there is no need actually to solve that problem. $\endgroup$
    – gnasher729
    Commented Jan 21, 2017 at 16:59
  • $\begingroup$ @gnasher729 Not quite a beginners mistake but a reading mistake , I misread the question quicksort asked above , hence he gave the solution according to it which was pretty obvious.. $\endgroup$
    – Ayush Goyal
    Commented Jan 21, 2017 at 18:13
  • 1
    $\begingroup$ Could you clarify what the output is supposed to be? You've commented on an answer that it's not calculating the right thing but the answer looks like a perfectly reasonable interpretation of what you've written. $\endgroup$
    – David Richerby
    Commented Jan 21, 2017 at 19:08

2 Answers 2

Reset to default
3
$\begingroup$

Finding all the triplets is in fact useless. Let $|A| = n$. Observe that each $a \in A$ appears in exactly $\binom{n-1}{2}$ triplets.

Therefore, the requested sum is just:

$$ \sum_{a \in A} \binom{n-1}{2}a = \binom{n-1}{2} \sum_{a \in A} a $$

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ ... and calculated in O (n). $\endgroup$
    – gnasher729
    Commented Jan 21, 2017 at 16:56
  • $\begingroup$ Hey, I think i misread you question above , I want the sum of every triplet individually like {1,2,3}=1+2+3=6 {1,2,4}=1+2+4=7 $\endgroup$
    – Ayush Goyal
    Commented Jan 21, 2017 at 18:11
  • $\begingroup$ @AyushGoyal, I'm officially confused. Can you please state your problem formally? What output would you like exactly? If you need even just one symbol per triplet, then you're bound to a solution in $\Omega(n^3)$, as there are $\binom{n}{3} \in \Theta(n^3)$ triplets. $\endgroup$
    – quicksort
    Commented Jan 21, 2017 at 18:24
1
$\begingroup$

Let n be the length of the array A

for (i = 0, i < n - 2, i++)
     for (j = i + 1, j < n - 1, j++)
          for (k = j + 1, k < n - 0, k++) 
               sum += i + j + k

You are iterating each result exactly once. I don't think you are going to do better on the iteration. It is O($\binom{n}{3}$). You can get number from combination.

If you look at as every element will appear with every other pair (2) from a set of n-1 then combin(n-1,2) for each element. Just sum the array and multiply by that number.

$\sum_{a \in A} \binom{n-1}{2}$

Improve this answer
$\endgroup$

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