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.

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

  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.

Leave a Reply

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