CareerCup

don't sort, if the order of selected 50 students is preserved, then binary search in O(log N) time.
else, every other student must be compared. ==> O(N) time, (below code)

b = selected_boy;
count = 0;
for each student s: selected_list{
	if( s.rank < boy.rank)
		count++;
}
return count+1;

don't sort, if the order of selected 50 students is preserved, then binary search in O(log N) time.
else, every other student must be compared. ==> O(N) time, (below code)

b = selected_boy;
count = 0;
for each student s: selected_list{
	if( s.rank < boy.rank)
		count++;
}
return count+1;

Use the Partition Algorithm of QuickSort.- O(n)

Use the Partition function of QuickSort.- O(n)

Use the Partition function of QuickSort.- O(n)
Use the element whose rank is to be evaluated as the pivot.

Perspective - 1
Sort all those fifty Students/Ranks then the index of the student picked would tell you his relative position.

Perspective - 2
I am not sure, but is the question based on " Counting Sort " where you have a fixed range ( in this case 50 ) for a huge numbers of items to sort with ( in this case 100 students )

MBR: Students are picked randomly. So don't expect input in order..
Sringeri: Sorting is a costly operation which requires nlog(n)


Need to do something different here..

MBR: Students are picked randomly. So don't expect input in order..
Sringeri: Sorting is a costly operation which requires nlog(n)


Need to do something different here..

wat if i compare the rank of the 40th rank student to all other 49 students...will that giv an optimised sol???

1. The ranks of the students randomly selected will lie between 1-100. So use radix sort to sort the entries. This will take O(n) time.
2. So now the index of the element is the answer to our problem.

Use a bit array of size 100, for each of 50 students selected, set the bit of a particular student as soon as he is selected.
Now for a student's rank which is say i in 100 students, start from index 0 and move toward i, counting number of set bits, this will tell us the rank in 50.

shove all students into an array, unsorted - O(n) - and then count the number of students above or below the student you're looking for - O(n).

O(n).
Just go through all 50 students and increment a counter for every student that has a better ranking than 40.