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.

14 thoughts on “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.

Leave a Reply

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