# Solution to Count-Triangles by codility

17 Apr

Question Name: Count-Triangles or CountTriangles

This problem is nearly the same as the exercise in presentation of lesson 13.

Update on May 24, 2014: Thanks to @Adam. Fix a bug, which lower the performance.

### 18 Replies to “Solution to Count-Triangles by codility”

1. Adam says:

if the list is sorted why do we set third = 0 at every iteration of first? Shouldn’t we set third to first + 2? I think A[first] + A[second] will always > A[third] where third < first + 2.

• Sheng says:

Yes, you are right! That was a bug. I have updated it. Thanks!

• Charles says:

Maybe third = first + 2 should be in the second loop, and changed to third = second + 1 ?

• Sheng says:

Sorry, we could not. It will make the time complexity to be O(N^3).

• Amanda says:

Three loops normally leads to O(n^3), right? Did I miss something here?

• Sheng says:

Haha, that’s the tricky point. It is O(N^2), because the variable “third” (the same as “second”) is moving O(N) for each “first”.

2. Pa says:

Hi Sheng, great solution. Thank you!
Could you please explain line 12? I can’t understand how “result” can capture the number of triangle triplets…

• Sheng says:

For each round, the triangles include:
first, second, second + 1
first, second, second + 2
….
first, second, third – 2
first, second, third -1

3. sam says:

In the line :—
result += third – second – 1
why are you doing -1 ? what is the need for that ?

• Sheng says:

first is the first item for the triangles.
second is the the second item for the triangles.
All the elements between second (exclusive) and third (exclusive) could be the third item for the triangles.
third – second – 1 is the number of elements in the range (second, third), both excusive.

4. Richard says:

After the array is sorted, the index of a number is different from that in the unsorted array. In other words, three numbers may form a triangle but their index in the unsorted may not be in the increasing order. Can you explain this?

• Sheng says:

The order does not matter at all! It is a trick.
Or in other words, you could sort their index, and the result is what you want.

5. micropentium6 says:

I have a longer version coz there is a binary search, which is supposed to be faster than linear scan. I can’t prove it’s O(N^2), although codility said so.
Update: Oops, there is a flaw. Codility test cases didn’t complain though.

• Sheng says:

The loop-i and loop-j lead to O(N^2).

6. David says:

Why is this not working? (by performance). Only difference is, that I call initiate c in the second loop… which actually makes more sense to me.

• Sheng says:

I cannot see your complete code, since you did not follow the instructions to post code~
As far as I can see from your incomplete code, your solution (basically brute force solution) has a higher complexity. Please refer to the lesson 13’s presentation for more details (the link is provided in the blog).
Thanks!

7. Akhil Kumar Dundigalla says:

Hello Sheng,
How can i know what time and space complexity does the question require? Till now all the codility examples i have solved
required less than O(N^2) time complexity. So i was trying to solve this question within O(NlogN) time complexity but couldn’t succeed.
Then i looked at your solution and your time complexity is O(N^2). If i knew this before working on the problem i would have found it
easier. So is there a way to find out what the complexities the question requires?

• Sheng says:

Sorry, I did not notice the complexities of the question in advance. Giving the expected complexity would be a good hint in interview.