Solution to Triangle by codility

21 Jan

Question: http://codility.com/demo/take-sample-test/triangle

Question Name: Triangle

Update: we need two parts to prove our solution.

On one hand, there is no false triangular. Since the array is sorted, we already know A[index] < = A[index+1] <= A[index+2], and all values are positive. A[index] <= A[index+2], so it must be true that A[index] < A[index+1] + A[index+2]. Similarly, A[index+1] < A[index] + A[index+2]. Finally, we ONLY need to check A[index]+A[index+1] > A[index+2] to confirm the existence of triangular.

On the other hand, there is no underreporting triangular. If the inequality can hold for three out-of-order elements, to say, A[index]+A[index+m] > A[index+n], where n>m>1. Again, because the array is sorted, we must have A[index] < = A[index+m-1] and A[index+m+1] <= A[index + n]. So A[index+m-1] +A[index+m] >= A[index]+A[index+m] > A[index+n] >= A[index+m+1]. After simplification, A[index+m-1] +A[index+m] > A[index+m+1]. In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.

In addition, here is a Java solution.

79 Replies to “Solution to Triangle by codility

  1. I have a misunderstanding with either your solution or the problem.
    I tried this without sorting (assuming that I couldn’t, I almost-finished a DAC solution before the time ran out). It looks like your solution works, and all the rest of the inequalities hold as long as the encoded inequality holds. What I don’t understand is: wouldn’t a false triangular be possible, since after sorting, the inequality can hold for an out-of-order element, an index ordering that I assumed had to be preserved?

    • Let me answer your question in two parts.
      On one hand, there is no false triangular. Since the array is sorted, we already know A[index] < = A[index+1] <= A[index+2], and all values are positive. A[index] <= A[index+2], so it must be true that A[index] < A[index+1] + A[index+2]. Similarly, A[index+1] < A[index] + A[index+2]. Finally, we ONLY need to check A[index]+A[index+1] > A[index+2] to confirm the existence of triangular.
      On the other hand, there is no underreporting triangular. If the inequality can hold for three out-of-order elements, to say, A[index]+A[index+m] > A[index+n], where n>m>1. Again, because the array is sorted, we must have A[index] < = A[index+m-1] and A[index+m+1] <= A[index + n]. So A[index+m-1] +A[index+m] >= A[index]+A[index+m] > A[index+n] >= A[index+m+1]. After simplification, A[index+m-1] +A[index+m] > A[index+m+1]. In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.
      Hope this helps!

      • Hello,
        Thanks for you answers. Here is what is confusing me
        “Assume that:
        N is an integer within the range [0..100,000];
        each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

        The elements in the array can be negative, but you insist they are positive. Am I missing something?

        • For the given definition of triangular, it is impossible to include a negative number in a triangular (If A < B < C < 0, A + B always < C.). My code did not assume all input are positive, but will skip all of negative numbers.

    • Let put it this way.
      1) sort the Array
      2) to make a triangle:
      2i) We set the longest side of the triangle . Let’s say it is A[i]
      2ii) we need to find the two shorter sides that can add up to A[i], Obviously A[i-2], A[i-1 ] are the two biggest values that are left for choosing from. If A[i-2] + A[i-1] A[i] return true;

  2. Hi, I used this java solution in Codility, which looks very much like your solution but I only got 81% and I don’t know why:

    Any help would be appreciated. Thanks.

    • Because your posted code has some issue to show properly, I really do not know how to debug it. At least, it will fail in the overflow test. I appended a 100/100 Java solution in this post. Please refer it.

    • I think this is becouse of intiger range:
      there is a chance that : array[i] + array[i+1] > Integer.MAX_VALUE is true

    • ‘array[i] + array[i+1] > array[i+2]’ was the route I initially took too for checking the triangle as that is the format they use in stating the question, but if you do the check this way you have to add overflow checking code such as:
      if(A[i]>0&&A[i+1]>0&&A[i]+A[i+1]<0)return 1;
      if(A[i+1]<0&&A[i+2]=0)return 0;
      Even those overflow checks will only bring you to 93%.
      Using ‘array[i] > array[i+2] – array[i+1]’ as Sheng does neatly eliminates the overflow error cases.

      • There was a mistype here and it’s not letting me edit:
        if(A[i+1]<0&&A[i+2]=0)return 0; should be
        if(A[i+1]<0&&A[i+2]=0)return 0;

  3. I tried the follwoing code without sorting and it works. It has O(n) since there is no sorting included but th epage tells me that it has O(n*log(n)). Can you confirm this?

    EDIT BY ADMIN: the solution is NOT correct. Please see following comments for more information.

  4. Hi,
    It seems like the algorithm returns 1 for the array below, while it should return 0?
    A = [10, 14, 5, 1]
    I think it should return 0, because there’s no consecutive elements that satisfies the conditions given. What do you think?

  5. Sorry, I’m still a bit confused about this statement:
    A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N
    If this is the case, then the array [5, 2, 10, 1, 8] should not contains a triangular, because even though [5, 10, 8] is triangular, the P, Q and R indexes don't match the condition given above. Obviously, I'm wrong, because your solution results in 100% on codility, but I don't quite understand why… can you explain it in detail?
    Thanks

    • Hello, you simply get lost in the index. The order of the index does NOT matter at all.
      For your example, the P is 0, Q is 2, R is 4. That is it.

      • Right, P=0, Q=2 and R=4 in the original array, but you are sorting the array, that results in this new array: [1, 2, 5, 8, 10]. If you map the values of this new array to the indexes in the original array, you will have P=0, Q=4 and R=2, which does not follow the condition P < Q < R.
        Well, we could just look at it differently and invert Q and R, making it Q=2 and R=4 so we could pass that condition. But if we do that, instead of checking A[P] + A[Q] > A[R], we would have to check for A[P] + A[R] > A[B], which would invalidate your algorithm.
        Please help!

        • It has been fun! The conclusion I came up with is that the indexes P, Q, R can be anything, but equal. That’s what they meant by 0 <= P < Q < R < N.
          As for the sum condition, it still has to be A[P] + A[Q] > A[R], the reason being… that the array is sorted, so the other sums are pointless.
          Just sharing my findings, HTH.

    • The question is: why cannot we sort it? There is no limitation on sorting. And sorting is good for the time complexity requirement.
      In addition, three numbers are triangular if and only if:
      A + B > C
      A + C > B
      B + C > A
      (For simplification, we assume A, B, C are larger than 0.)
      After sorting, with any three consecutive (non-decreasing) integers A, B, C, we already know:
      A + C > B
      B + C > A
      Then, we only need to check A + B and C.
      With negative or zero numbers, it is similar.

        • Sure, it could sort in either case. If the function need to return the position index, you can build a struction to store both the index and the value(first is index, the second is the correponding value). For example, [0, 5], [1, 6], [2, 3], [3, 2] for input array [5, 6, 3, 2].
          Then we can do the same process.
          Finally, we return the index in the structures.

  6. Hello,
    In the question it states : 0 ≤ P < Q < R < N
    In this scenario after sorting could we not have something that resembles :
    [8 , 9 , 9 ,9 ,9 ,9]?
    In this case by the inequality above a triangle does no exist, correct?

    • Your posted code is incomplete due to the wordpress issue. It seems that your did not check the empty input and overflow when computing the sum.

  7. I don’t understand how extreme_empty(empty sequence) and extreme_single(single value) is expected to return 1. I return 0 for these test cases but it says it is wrong in C++ and should return 1.

    • I did not meet your problem. As far as I see, the “extreme_empty” and “extreme_single” are expected to return 0.

  8. I’m glad I came here again to find simpler solutions, I’ll post mine even though I noticed reading the previous post that it’s doing some unnecessary work by comparing the other cases in my isTriangular method. I got 100% on codility:

  9. C# 100, actually it is a copy of previous java version, all glory to Sheng

  10. Hi, you don’t need to check the length of A. The simplified solution below works fine:

  11. c++ solution got 100%

  12. Objective C solution

  13. Good explanation, but there’s no need to check if len(A) < 3. Since you're iterating over xrange(A_len-2), any A_len that is smaller than 3 will become zero or negative when you subtract the 2. xrange(x) where x < 1 will be empty, i.e. not a single iteration will happen, and solution() will return 0.
    By the way, note that you don't need the initial 0 in xrange(0, A_len-2) – it is the default, so xrange(A_len-2) is equivalent.

  14. What would you do if the array wasn’t sorted?
    In the problem description I can’t find that assumption…
    A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R A[R],
    A[Q] + A[R] > A[P],
    A[R] + A[P] > A[Q].
    For example, consider array A such that:
    A[0] = 10 A[1] = 2 A[2] = 5
    A[3] = 1 A[4] = 8 A[5] = 20
    Triplet (0, 2, 4) is triangular.
    Write a function:
    class Solution { public int solution(int[] A); }
    Even the example is unsorted, and sorting it, wouldn’t guarantee the condition:
    0 ≤ P < Q < R < N
    Which are indexes, not values..

  15. Hey Sheng,
    First of all great site. After I find my own solution, I check your site for answers. I couldn’t understand this “In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.” Do we need to check this as well?
    Further, if we modify the question to find the all the triangles in a given array, then I believe we also need to check for out of order elements as well.

    • Hi Laaptu, thanks for visiting!
      The whole paragraph before “In other words, …” is used to prove this statement. Because we ONLY need to check the existence, we do not need to check all combinations.
      And you are right, if we are going to find all the triangles, we need to check all.

  16. javascript solution got 100%

  17. javascript solution 100%

  18. Checking just the central elements is enough it seems.

    • The solution is apparently wrong. Please try [1, 1, 1, 1, 5, 5, 5].
      PS: it’s totally by coincidence that your solution could pass the tests.

  19. – My solution is correct except that it runs int O(N^3) time.

  20. Maybe I’m wrong, but I feel that the assume at the start is not correct. At first glance all the solutions are check neibouring values, but I’m now sure about about that, since the array can contain duplicates. For example values [1, 1, 1, 10, 10, 10, 12] does not having triangular:

    1 + 10 > 12 failed
    10 + 12 > 1 success
    12 + 1 > 10 success

    But your solution gives 1 as an answer since you’re checking the 10 + 10 > 12

    UPDATE:
    I’m not sure, but it seems that not all of your sugesssuins is right. Soring arrays is a good point? but doint forget it can contain duplacates so it is not enough just to check neigbouring elements. For example is you check array [1, 10, 12] it is not valid triangular:

    1 + 10 > 12 failed
    10 + 12 > 1 success
    12 + 1 > 10 success

    And you code will return 0. And that is correct. But if you check an array of [1, 1, 10, 10, 12] it will give 1 because you check 10 + 10 > 12!

    • I do not quite understand your concern. In input [1, 1, 10, 10, 12], [10, 10, 12] is actually a valid triangle, right?

      In the problem description: A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and .... P, Q, R is some index, not the value. The A[P], A[Q], and A[R] can hold the same value.

      • Hi Sheng,

        In the same example [1, 1, 10, 10, 12], as per your statement [10, 10, 12] is valid.
        Isn’t [1,10,10] also a valid triangle. Am i going in the wrong direction. Please explain.

        • [1,10,10] is a valid triangle.

          The question is: returns 1 if there exists a triangular triplet for this array and returns 0 otherwise

          If there are 1, or 2, or more triagnular, the code should return 1.

  21. sorry forgot to write my code in the tags.

    Can you please explain what’s wrong with my code?

  22. 100% javascript solution

  23. Hi all
    thanks for this blog: it’s really amazing, encouraging and supporting !!! 😀
    1) <=0 side cannot belong to a triangle right ? (codility says "A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N" I think it should be 0<P …) neither a triangle may have 2 or 3 equal sides
    2) while I understand that the exercise only requests whether there is at least 1 triangle within the set of sides, I have compared all triangles extracted by the algorithm you shared with the ones extracted by a more exhaustive search and I find a number more: isn't this a potential underreporting ?

    e.g. this few cases:
    A: [1, 2, 5, 6, 7]
    exhaustive: [2,5,6, 2,6,7, 5,6,7]
    fast: [2,5,6, 5,6,7]

    A: [1, 4, 5, 6, 8]
    exhaustive: [4,5,6, 4,5,8, 4,6,8, 5,6,8]
    fast: [4,5,6, 5,6,8]

    • You are very welcome!

      RE: codility says “A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N” I think it should be 0 < P …
      P, Q, R is the index, NOT the value. There is no restriction about the range of A[P] A[Q] or A[R].

      RE: isn’t this a potential underreporting?
      Yes, you are right. My algorithm does not find out ALL the triangular, but is enough to determine the triangular’s existence.

  24. I initially solved it using how Sheng did to just find the mere existence of a trianglular. My code can be modified to find all triplets though. Python 100%. Detected time complexity O(N*logN). Please feel free to comment. Thanks.

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!