Solution to Count-Triangles by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_triangles

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. 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.

  2. 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…

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

    • 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.

  3. 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?

    • 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.

  4. 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.

  5. 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.

    • 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!

  6. 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?

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!