We have "n" sticks with us. The length of each stick is known to us. We need to find the number the triangles that can possibly be made from these sticks. The condition for making a triangle is that the sum of any two sides of the triangle should be greater than the third side. i.e. if a, b, c form a triangle, then :
1) a+b>c
2) b+c>a
3) a+c>b
INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".
OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.
BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have nC3 = ϴ(n3) comparisons. Following is the brute force approach:
Algorithm bruteForce(int[n] a)
1. For (i = 0 upto n-3)
2. For(j = i+1 upto n-2)
3. For(k = j+1 upto n-1)
4. if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5. count++
A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then (a, b, c) can form a triangle.
This manipulation is illustrated as follows :
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.
The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.
Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n3. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.
1) a+b>c
2) b+c>a
3) a+c>b
INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".
OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.
BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have nC3 = ϴ(n3) comparisons. Following is the brute force approach:
Algorithm bruteForce(int[n] a)
1. For (i = 0 upto n-3)
2. For(j = i+1 upto n-2)
3. For(k = j+1 upto n-1)
4. if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5. count++
A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then (a, b, c) can form a triangle.
This manipulation is illustrated as follows :
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.
The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.
Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n3. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.
No comments:
Post a Comment