# Solution to Triangle by codility

21 Jan

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.

### 66 Replies to “Solution to Triangle by codility”

1. meatcomputer says:

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?

• Sheng says:

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!

• Sandeep says:

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?

• Sheng says:

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.

• Jim says:

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. VJKS says:

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.

• Sheng says:

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.

• Ivan says:

Do the sorting after the validation and cast to long everything in the sum.

• Sheng says:

Sorry, I didn’t catch your idea.

• ktoslepszy says:

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

3. Rob says:

>>Since the array is sorted, we already know A[index] < = A[index+1] A[index+n]

Can you explain that in more detail?

Thanks!

• Sheng says:

Sorry, it might be a bad description. We sort the array as the first step. So we are sure it is sorted in all the discussion.

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?

• Sheng says:

Codility.com can only estimate the complexity. Your solution is O(N).

I cannot find a counterexample for your solution. I cannot proof it neither. Sorry! If you find a solution, please do tell me. Thanks!

• Wei says:

Hi, I tried [2,4,5,10] using Behzad’s method. it is supposed to return 0, right? but the method will return 1. So this is a counter example right?

• Sheng says:

It is supposed to return 1, because there is a triangle [2, 4, 5].

• for the input [1, 1, 2, 3, 5] the solution returned a wrong answer (got 1 expected 0).

• Sheng says:

Thanks for providing a counter-example.

I’m not a serious programmer but I do it for the fun. But rather like the Math. I’ll look if I can find a proof for it.

• Sheng says:

Fun will turn you to be an expert programmer ðŸ™‚

6. Henrique says:

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?

• Sheng says:

Hi!

There is no requirement that, they need to be consecutive. And the [10. 14. 5] is a triangular.

• Henrique says:

In the first paragraph, they say: A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N

• Henrique says:

Oh, doh! I see where I failed, sorry!

• Sheng says:

That is fine. To err is human.

Enjoy coding!

7. Henrique says:

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

• Sheng says:

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.

• Henrique says:

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.

• Henrique says:

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.

• Sheng says:

I am glad that you got the idea! It is tricky.

• This has been confusing me as well. I groaned when I realized P < Q < R only says they're not equal, since they're all interchangeable in the next part of the parameters.

8. Dan says:

One question: why are we allowed to sort the array ?

• Sheng says:

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.

• Dan says:

Would it still be allowed to sort if the function should return the triangle positions A,B and C ?

• Sheng says:

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.

9. Karl says:

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?

• Sheng says:

IMO, the triangles exist a lot. For example, (9, 9, 9) is a triangle.

• True, codility is wrong. They mention P+Q>R, but forget that P+Q>=R will also work.

• Sheng says:

How could they construct a triangle, if A[P] + A[Q] == A[R]? It’s impossible.

10. lei says:

i use the same method , but C++. why my code can’t be accepted. can you help me ?

• Sheng says:

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.

11. Thomas says:

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.

• Sheng says:

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

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

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

• Sheng says:

Thanks Kembl!

14. Mathieu says:

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

• Sheng says:

You are totally right! Thanks for sharing!

15. dwitee panda says:

c++ solution got 100%

16. Khurram Awan says:

Objective C solution

17. Someone says:

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.

• Sheng says:

You are totally right. Thanks very much for your suggestions!

18. Dnait2 says:

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

• Sheng says:

That’s why I sorted the input array firstly.

19. laaptu says:

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.

• Sheng says:

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.

• laaptu says:

Awesome. Thanks

20. Manuel says:

javascript solution got 100%

21. Manuel says:

javascript solution 100%

22. Dimitri says:

Checking just the central elements is enough it seems.

• Sheng says:

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.

23. Rafael says:

Solution that works with negative numbers:

• Sheng says:

Please refer to the “Guideline for Comments” on the right column for posting code. Thanks!

24. Ramazan says:

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

25. isa says:

lol, I tried so hard implementing a good sorting algorithm, when apparently it is allowed to use A.sort(), I was a fool.

• Sheng says:

No, you were just practicing with a sorting algorithm ðŸ˜‰