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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def solution(A): A_len = len(A) if A_len < 3: # N is an integer within the range [0..1,000,000] # if the list is too short, it is impossible to # find out a triangular. return 0 A.sort() for index in xrange(0, A_len-2): if A[index]+A[index+1] > A[index+2]: return 1 # The list is sorted, so A[index+i] >= A[index+2] # where i>2. If A[index]+A[index+1] <= A[index+2], # then A[index]+A[index+1] <= A[index+i], where # i>=2. So there is no element in A[index+2:] that # could be combined with A[index] and A[index+1] # to be a triangular. # No triangular is found return 0 |

In addition, here is a Java solution.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | // you can also use imports, for example: // import java.math.*; import java.util.Arrays; class Solution { /** * Check whether there is a triangular * @param A The array for length of lines * @return 0: no triangular found * 1: triangular is found */ public int solution(int[] A) { // Handle with the special cases if(null == A || A.length < 3) return 0; // Sort the input, and then try to find the triangular Arrays.sort(A); for(int i = 0; i < A.length-2; i++) { // Beware of overflow if (A[i] >= 0 && A[i] > A[i+2] - A[i+1]) { return 1; } /* * We already know A[i+1] <= A[i+2]. If A[i] < 0, * A[i] + A[i+1] < A[i+2] */ } return 0; } } |

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

ONLYneed 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

MUSThaveAT LEASTan 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;

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.

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

Sorry, I didn’t catch your idea.

I think this is becouse of intiger range:

there is a chance that : array[i] + array[i+1] > Integer.MAX_VALUE is true

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

Can you explain that in more detail?

Thanks!

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?

EDIT BY ADMIN: the solution isNOTcorrect. Please see following comments for more information.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!

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?

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

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.

Fun will turn you to be an expert programmer 🙂

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?

Hi!

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

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

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

Thanks for answering!

That is fine. To err is human.

Enjoy coding!

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

originalarray, 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, whichdoes notfollow the conditionP < 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.

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.

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

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.

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

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.

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?

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.

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

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

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.

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.

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:

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

Thanks Kembl!

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

You are totally right! Thanks for sharing!

c++ solution got 100%

Objective C solution

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.

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

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

That’s why I sorted the input array firstly.

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.

Awesome. Thanks

javascript solution got 100%

javascript solution 100%

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.

Solution that works with negative numbers:

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