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
public class Solution {
public int nTriang(int[] arr) {
int MOD = 1_000_000_007;
Arrays.sort(arr);
int n = arr.length;
long count = 0;
for (int i = n - 1; i >= 1; --i) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[j] + arr[k] > arr[i]) {
count = (count + k - j) % MOD;
k--;
} else
j++;
}
}
return (int) count;
}
}
Last updated