https://codility.com/programmers/lessons/13
Also check Count the number of possible triangles | GeeksforGeeks
// O(n^2)
//https://codility.com/demo/results/demoHFCK86-FBV/
public int solution(int[] A) {
Arrays.sort(A);
int ans = 0, n = A.length;
for (int i = 0; i < n - 2; i++) {
int k = 0; // k is init here
for (int j = i + 1; j < n - 1; j++) {
while (k < n && A[i] + A[j] > A[k]) {
k++;
}
ans += k - j - 1;
}
}
return ans;
}
// O(n^3)
//https://codility.com/demo/results/demoHVJ2YB-D56/
/*public int solution(int[] A) {
Arrays.sort(A);
int ans = 0, n = A.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = A[i] + A[j];
for (int k = j + 1; k < n && A[k] < sum; k++) {
ans++;
}
}
}
return ans;
}*/
http://www.geeksforgeeks.org/find-number-of-triangles-possible/
http://www.martinkysel.com/codility-counttriangles-solution/
Also check Count the number of possible triangles | GeeksforGeeks
A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, 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] = 12
There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).
Write a function:
int solution(int A[], int N);
that, given a zero-indexed array A consisting of N integers, returns the number of triangular triplets in this array.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12
the function should return 4, as explained above.
http://codility-lessons.blogspot.com/2015/03/lesson-13-counttriangles-count-triangles.htmlFirst we sort the given array.
If we search the triangles from this sorted array, we only have to check if A[P] + A[Q] > A[R], because it is always A[P] <= A[Q] <= A[R]. A[P] < A[Q] + A[R] and A[R] + A[P] > A[Q] are always hold.
We check P from the beginning. When we check P, first we set Q just to the next to P, and R to the next to Q. We can slide R while A[P] + A[Q] > A[R] is hold and every time we slide R, we can have (R - Q) combinations for (P, Q, R).
(Why? suppose you have a certain location of R, then Q can be any place between P and R, since Q is just getting larger and this does not invalidate A[P] + A[Q] > A[R]).
If we can not slide R anymore, then we slide Q to the next position. If it becomes Q==R, then slide R again.https://github.com/acprimer/Codility/blob/master/src/Lesson13/CountTriangles.java
// O(n^2)
//https://codility.com/demo/results/demoHFCK86-FBV/
public int solution(int[] A) {
Arrays.sort(A);
int ans = 0, n = A.length;
for (int i = 0; i < n - 2; i++) {
int k = 0; // k is init here
for (int j = i + 1; j < n - 1; j++) {
while (k < n && A[i] + A[j] > A[k]) {
k++;
}
ans += k - j - 1;
}
}
return ans;
}
// O(n^3)
//https://codility.com/demo/results/demoHVJ2YB-D56/
/*public int solution(int[] A) {
Arrays.sort(A);
int ans = 0, n = A.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = A[i] + A[j];
for (int k = j + 1; k < n && A[k] < sum; k++) {
ans++;
}
}
}
return ans;
}*/
http://www.geeksforgeeks.org/find-number-of-triangles-possible/
Method 1 (Brute force)
The brute force method is to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from array, the innermost loop checks for the triangle property ( the sum of any two sides must be greater than the value of third side).
The brute force method is to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from array, the innermost loop checks for the triangle property ( the sum of any two sides must be greater than the value of third side).
Time Complexity: O(N^3) where N is the size of input array.
Method 2 (Tricky and Efficient)int findNumberOfTriangles(int arr[], int n){ // Sort the array elements in non-decreasing order qsort(arr, n, sizeof( arr[0] ), comp); // Initialize count of triangles int count = 0; // Fix the first element. We need to run till n-3 as the other two elements are // selected from arr[i+1...n-1] for (int i = 0; i < n-2; ++i) { // Initialize index of the rightmost third element int k = i+2; // Fix the second element for (int j = i+1; j < n; ++j) { // Find the rightmost element which is smaller than the sum // of two fixed elements // The important thing to note here is, we use the previous // value of k. If value of arr[i] + arr[j-1] was greater than arr[k], // then arr[i] + arr[j] must be greater than k, because the // array is sorted. while (k < n && arr[i] + arr[j] > arr[k]) ++k; // Total number of possible triangles that can be formed // with the two fixed elements is k - j - 1. The two fixed // elements are arr[i] and arr[j]. All elements between arr[j+1] // to arr[k-1] can form a triangle with arr[i] and arr[j]. // One is subtracted from k because k is incremented one extra // in above while loop. // k will always be greater than j. If j becomes equal to k, then // above loop will increment k, because arr[k] + arr[i] is always // greater than arr[k] count += k - j - 1; } } return count;}http://www.martinkysel.com/codility-counttriangles-solution/
