Question:
Find the number of triangles that can be formed with three different array elements as three sides of triangles, for a given unsorted array of n elements.
Example:
Input : [5, 4, 3, 1, 2,6,8,7,9]
Output: Yes
Sides of the possible triangle are <1,2,3>,<2,3,4>,<3,4,5>,<4,5,6>,<5,6,7>,<6,7,8>.
Solution:
Approach:1. Sort the array in increasing order.
2. Initialize
i = 0; // First Element
j = 1; // Second Element
count = 0; // Number of triangles
3. WHILE (i<n-2)
k = j+1;
move k forward until arr[k] becomes > (arr[i] + arr[j]) or k moves out of bound
count = count +1
increment j
if j is at end of array
increment i and set j=i+1
4. Print count.
C program:
// C program to find if it is possible to form a
// triangle from array values and Display it and count it.
#include <stdio.h>
// Method prints possible triangle when array values
// are taken as sides
int isPossibleTriangle(int arr[],int N)
{
int i,j,swap,flag=0,count=0;
// If number of elements are less than 3, then no
// triangle is possible
if (N < 3)
return 0;
// first sort the array
for(i=0;i<N;i++)
{
for(j=i+1;j<N;j++)
{
if(arr[i]>arr[j])
{
swap=arr[j];
arr[j]=arr[i];
arr[i]=swap;
}
}
}
// loop for all 3
// consecutive triplets
for ( i = 0; i < N - 2; i++)
// If triplet satisfies
// triangle condition that a+b>c
if (arr[i] + arr[i + 1] > arr[i + 2])
{
printf("<%d,%d,%d>\n",i,i+1,i+2);
count++;
}
return count;
}
int main()
{
int arr[] = {5, 4, 3, 1, 2,6,8,7,9};
int N = sizeof(arr) / sizeof(int);
int a=isPossibleTriangle(arr, N);
if(a>1)
printf("Yes: No of triangle that can formed=%d",a);
else
printf("No");
return 0;
}
Output:
<1,2,3>
<2,3,4>
<3,4,5>
<4,5,6>
<5,6,7>
<6,7,8>
Yes: No of triangle that can formed=6
0 comments:
Post a Comment