in Algorithms edited by
17,623 views
58 votes
58 votes

An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array 

  1. solves it in linear time using a left to right pass of the array
  2. solves it in linear time using a right to left pass of the array
  3. solves it using divide and conquer in time $\Theta (n\log n)$
  4. solves it in time $\Theta( n^2)$
in Algorithms edited by
17.6k views

4 Comments

This Program will also work to find all such LEADER.

 

#include<stdio.h>
#include<conio.h>

void main()
{int i;
 int a[]={10,2,5,7,3,1,4,3};
 int temp=0;
 for(i=sizeof(a)/sizeof(int)-1;i>=0;i--)
 {if(a[i]>temp)
   { printf("%d ",a[i]);
     temp=a[i];
   }
 }
getch();
}
0
0

By right to left pass of the array we can do in O(n) time.

#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
	int n;
	scanf("%d",&n);
	int a[n],max;
	for(int i=0;i<n;i++){
		scanf("%d ",&a[i]);
	}	
	max=a[n-1];
	printf("leaders are = %d ",max);
	for(int i=n-2;i>=0;i--){
		if(a[i]>max){
			max=a[i];
			printf("%d ",max);			
		}
	}
	return 0;
}

https://ideone.com/ejaIFg

 

By left to right pass of the array we can do in O(n^2) time.

#include <iostream>
#include<stdio.h>
using namespace std;

int main() {
	int n;
	scanf("%d",&n);
	int a[n],max,count;
	for(int i=0;i<n;i++){
		scanf("%d ",&a[i]);
	}	
	printf("leaders are =");
	for(int i=0;i<n;i++){
		count=1;
		for(int j=i+1;j<n;j++){
			if(a[i]<a[j]){
				count=0;
			}
		}
		if(count==1){
			printf("%d ",a[i]);
		}
	}
	return 0;
}

 

https://ideone.com/fupNEv

 

 

1
1
They pretty much handed out a huge hint in the options.
1
1

7 Answers

0 votes
0 votes

I think, that this problem is only reverse sorting or putting elements in descending order,

In order to do that start scanning from right.

So. ANSWER is B.

0 votes
0 votes

I have fully explained this question and gave the answer in short period of time just go through the link.

I hope it’ll help you

https://youtu.be/hu9RWj1YxEY

–1 vote
–1 vote

Use two loops. The outer loop runs from 0 to size – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.

#include<iostream>

using namespace std;

/*C++ Function to print leaders in an array */

void printLeaders(int arr[], int size)

{

    for (int i = 0; i < size; i++)

    {

        int j;

        for (j = i+1; j < size; j++)

        {

            if (arr[i] <= arr[j])

                break;

        }   

        if (j == size) // the loop didn't break

            cout << arr[i] << " ";

  }

}

/* Driver program to test above function */

int main()

{

    int arr[] = {16, 17, 4, 3, 5, 2};

    int n = sizeof(arr)/sizeof(arr[0]);

    printLeaders(arr, n);

    return 0;

}

3 Comments

Ur coding will take O($n^{n}$) in worst case .... Bt the answer should be O($n$) ....
0
0
@puja for option a y it can't be n*n for n elements we are traversing n times approximately so n*n how will u conclude it will be n^n plzzzzzz tell me if I'm wrong let me know how to think
0
0
Why n*n we traversing from right to left one time so it should be o(n).

If they ask worst case then o(n^2)
0
0
Answer:

Related questions