0

Given an array of elements. An element is called as a leader if it is greater than all
the elements to the right of it. Print all the leaders in O(n)?

The following is my approach.Can anyone tell me how to improve the code and also the current time complexity?
Is recursion more efficient in this case?

#include<stdio.h>
void findLeaders(int a[],int n)
{
 int i,j=n-1,flag=0;
 for(i=0;i<n;i++)
 {
   if(a[i] > a[i+1])
   {
	while(a[i]>a[j])
	{
		if((i+1) ==j) 
		{
			flag=1;
			printf("\nleader = %d",a[i]);
		        break;
		}
		else   j--;
	}
	j=n-1;
   }
 }
 if(!flag)  printf("\nNo leader in the given array\n");
}
 

int main()
{
 int a[100],n=0,i=0;
 printf("\nEnter n:");
 scanf("%d",&n);
 for(i=0;i<n;i++)
	scanf("%d",&a[i]);
 findLeaders(a,n);
 printf("\n\n");
 return 0;
}

Thanks in advance.

Edited by want_to_code: more information

3
Contributors
4
Replies
6
Views
8 Years
Discussion Span
Last Post by thines01
0

Yes, start at the RIGHT-most (highest) element and work your way backwards.

When you run across a value that's higher, it's a leader.

1
#include <stdio.h>

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];

	for(int i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
void main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}
}
Votes + Comments
That's it.......A very good solution
0
#include <stdio.h>

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];

	for(int i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
void main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}
}

i heard that bool is supported by gcc compiler ( for a c program)
but when i saved this file in .c extension and executed, it gave me errors as bool is unrecognized identifer.

is there any special header we need to include for that.

0

you can use "int" or you can use a typedef
typedef enum {false, true} bool;

This version will compile under gcc:

// ParseLeaders.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

typedef enum {false, true} bool;

bool findLeaders(int a[],int n)
{
	bool flag = false;
	int intHighest = a[n-1];
	int i=0;

	for(i=(n-2); i >= 0; i--)
		{
		if(a[i] > intHighest)
			{
			flag = true;
			printf("\nleader = %d", a[i]);
			intHighest = a[i];
			}
		}
	return flag; // returns fals if no leaders
}
int main(void)
{
	static int a[] = {5,1,2,7,3,4,6};
	static int b[] = {9,1,2,8,3,4,6,7};

	if(!findLeaders(a, (sizeof(a)/sizeof(int))))
		{
		puts("No Leaders in a");
		}

	if(!findLeaders(b, (sizeof(b)/sizeof(int))))
		{
		puts("No Leaders in b");
		}

	return 0;
}

Edited by thines01: clarity

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.