Solution to Codility lesson4-exercise2 Triangle problem, link to Codility problem and complete solution at the end of the post.
Definitions:
A triplet
is triangular if
and:
- A[P] + A[Q] > A[R],
- A[Q] + A[R] > A[P],
- A[R] + A[P] > A[Q].
Just like in the Max Product of Three problem,
only means that you can’t use the same element of A.
Problem:
Define a function solution with input A, such that solution returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
- Expected worst-case time complexity is O(N*log(N));
- Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Analysis:
To solve this problem we have to sort the array first, in Python this can be done using A.sort(), the sort method in Python has a time complexity of O(N*log(N)).
With the array sorted now we can solve the problem with O(N) time complexity, we just have to iterate through A, check if A[k], A[k + 1], A[k + 2] is triangular, if it is we return 1 and if not we go to next k, until we finish the array.
13 14 15 16 |
# Since Array is sorted, only have to look for each element once for k in xrange(N - 1): if test_triangle(A[k], A[k + 1], A[k + 2]): return 1 |
The test_triangle function checks if the triple is triangular.
20 21 |
def test_triangle(P, Q, R): return (P + Q) > R and (Q + R) > P and (R + P) > Q |
So why does this work? First when we sorted the array we modified most of the elements’ indexes. And this may seem to broke this statement
. But let’s say that,
and that
is triangular, this means that
but you can try yourself and see that this holds for every combination of
and
, for example for
, so it’s only a matter of rearranging the elements to make the statement
true. The second thing to prove is, if A[k], A[k + 1], A[k + 2] is not triangular, why didn’t we tested for A[k], A[k + 2], A[k + 3] and so forth. Well this can be answered by the fact that A is now sorted. We know that
, so in our function test_triangle what we are really testing is if
, if it’s not there is no need to test the next elements since every other element is greater or equal than
. And to prove that we only need to test if
. Assume that
, this means that
which can not be true. The same goes for
.
The total time complexity is O(N) + O(N*log(N)) = O(N*log(N)).
For the space complexity we have O(1).
Complete Solution:
12345678910111213141516171819202122
# Name: Triangle# Link: https://codility.com/demo/take-sample-test/triangle/ def solution(A): N = len(A) A.sort() # If A length is lesser than 3 A can't be triangular if N < 3: return 0 # Since Array is sorted, only have to look for each element once for k in xrange(N - 1): if test_triangle(A[k], A[k + 1], A[k + 2]): return 1 return 0 def test_triangle(P, Q, R): return (P + Q) > R and (Q + R) > P and (R + P) > Q
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# Name: Triangle # Link: https://codility.com/demo/take-sample-test/triangle/ def solution(A): N = len(A) A.sort() # If A length is lesser than 3 A can't be triangular if N < 3: return 0 # Since Array is sorted, only have to look for each element once for k in xrange(N - 1): if test_triangle(A[k], A[k + 1], A[k + 2]): return 1 return 0 def test_triangle(P, Q, R): return (P + Q) > R and (Q + R) > P and (R + P) > Q |
Time Complexity O(N*log(N))
Space Complexity O(1)