-
Notifications
You must be signed in to change notification settings - Fork 9
/
CountingTriangle.cpp
35 lines (33 loc) · 1.27 KB
/
CountingTriangle.cpp
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
/*
Counting Triangles
You are given an array of N non-negative integers, A0, A1 ,..., AN-1. Considering each array element Ai as the edge length of some line segment, count the number of triangles which you can form using these array values. Notes:
You can use any value only once while forming each triangle. Order of choosing the edge lengths doesn't matter. Any triangle formed should have a positive area.
Return answer modulo 109 + 7.
For example,
A = [1, 1, 1, 2, 2]
Return: 4
*/
// Use two pointer to track what range could form valid triangles
int Solution::nTriang(vector<int> &A)
{
int n = A.size();
int num = pow(10, 9) + 7;
sort(A.begin(), A.end());
int count = 0;
for (int i = n - 1; i >= 1; i--)
{ // Loop through all elements
int l = 0, r = i - 1;
while (l < r)
{ // while l < r && sum of A[l] + A[r] > A[i] that means it could form a valid triangle
//so all the elemnts between l+1 and r-1(inclusive) could also form valid triabgle, so count+=(r-l)
if (A[l] + A[r] > A[i])
{
count = (count + (r - l) % num) % num; // take mod of subtraction and the mod of sum as well
r--;
}
else
l++;
}
}
return count;
}