Program to find leader in an array
Everything in the right should be smaller than current element.Two method are there.First method is brute force method but the complexity is O(n^3).But the method 2 is optimal solution that complexity is O(n).
For example
a[4]={1,5,4,3}
In the given array 1 is not leader because all the element right from 1 is greater.
5 is leader element because all the element from right from 5 is smaller than 5.
4 and 3 is also leader element.
So leader element is {5,4,3}
Method 1: brute force to find leader in a array.
#include<stdio.h>
void main() {
int a[4]={1,5,4,3};
int n=4;
int i,j;
int flag;
int ans[3];
for(i=0;i<n;i++)
{
flag=1;
for(j=i+1;j<n;j++)
{
if(a[j]>a[i])
{
flag=0;
break;
}
}
if(flag==1)
printf("%d",a[i]);
}
}
Output
5
4
3
Brute force solution is not good because complexity O(n^3)
Method 2:Optimal solution to find leader in array.
#include<stdio.h>
void main() {
int a[4]={1,5,4,3};
int n=4;
int i;
int max=0;
for(i=n-1;i>0;i--)
{
if(a[i]>max)
{
printf("%d",a[i]);
max=a[i];
}
}
}
Output
5
4
3
But the method 2 is optimal solution that complexity is O(n).
0 Comments