-
Notifications
You must be signed in to change notification settings - Fork 1
/
lesson6_3_Triangle.rb
47 lines (35 loc) · 1.26 KB
/
lesson6_3_Triangle.rb
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
# A[P] + A[Q] > 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:
# def solution(a)
# that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
# For example, given array A such that:
# A[0] = 10 A[1] = 2 A[2] = 5
# A[3] = 1 A[4] = 8 A[5] = 20
# the function should return 1, as explained above. Given array A such that:
# A[0] = 10 A[1] = 50 A[2] = 5
# A[3] = 1
# the function should return 0.
# Write an efficient algorithm for the following assumptions:
# 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].
def solution(a)
arr = a.select{|x| x >=0 }.sort
arr.each_with_index do |p, pi|
arr[(pi+1)..-1].each_with_index do |q, qi|
arr[(qi+pi+2)..-1].each do |r|
break if p+q <=r
break if p+r <=q
break if r+q <=p
return 1
end
end
end
0
end