Answer to Question #226990 in Java | JSP | JSF for Ayush

Question

x Number of players are participating in a sporting event.They are standing in a row.
Each player has some match value associated with them. Now each player wants to make one
friend on their right side having greater match value as compared to him and it should be the
nearest player as well to him.
Your task is to print for each player their friend’s index and his match value. If a player is not
able to make such a friend print -1.
a) Find an Algorithm of Complexity O(n^2) to solve this problem.
b) Find an efficient way to compute the friends in O(n) Complexity.
Assume 1-based indexing.

Answer 1

a)
Algorithm
Input:
an array of x number of players 
Output:
player, friend's index and match value
Explanation.
For every n there is n*n operations O(n^2).
O(n^2) complexity is always demostrated using two loops.
//Let us assume x = 6. But you can change the value of x
	int arr[6]= {5,6,7,8,9,10}; //Array containing the players' match value
	int arr1[6];


	int n;
	n = 6; //Putting the number of players to be six
	for(int i=0; i<n; i++){ //First loop to perform n operation
		int index;
		for(int j=1; j<=n; j++){ //Second loop to perform n *n operations
			
			if(arr[i] < arr[j+1]){
				index = i;
				cout<<index<<endl;
			}
			
		}
	}
b)
O(n)- This type complexity runs in linear time and n is the number of elements
in the array. This kind of complexity has only one loop.
For this problem, the perfect algorithm can be:
//Let us assume x = 6. But you can change the value of x
	int arr[6]= {5,6,7,8,9,10}; //Array containing the players' match value
	int arr1[6];


	int n;
	n = 6; //Putting the number of players to be six
	for(int i=0; i<n; i++){ //Loop to perform n operations
	int index;
	if(arr[i]<arr[i+1]){
		index = i;
	}
	cout<<index;
	}