Student Percentile Calculation

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array of student marks. Your task is to calculate the percentile for each student based on the following rule:

The percentile of a student is the percentage of students having marks strictly less than their own. The denominator for this calculation should be the total number of other students (N-1).

The formula is:

Percentile = floor( (Number of students with marks < current student's marks) * 100 / (N - 1) )

Your function should return an array containing the percentile for each student, corresponding to their original order in the input array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of students.

The second line contains N space-separated integers, representing the marks of each student.

Output Format:

Your function should return a list/array of integers representing the percentile of each student in the original order.

Note:

The calculation uses integer division, so any fractional part is truncated.

If N <= 1, a percentile is not well-defined. In this case, your function should handle it appropriately (e.g., return [0]).

An O(N^2) brute-force solution may be too slow. An O(N log N) solution using sorting is more efficient.

Sample Input 1:

5
12 60 80 71 30

Sample Output 1:

0 50 100 75 25

Explanation for Sample 1:

There are N=5 students, so the denominator is 5-1=4.
  Student with marks 12: 0 students have marks less than 12. (0 * 100) / 4 = 0.
  Student with marks 60: 2 students (12, 30) have marks less than 60. (2 * 100) / 4 = 50.
  Student with marks 80: 4 students (12, 30, 60, 71) have marks less than 80. (4 * 100) / 4 = 100.
  Student with marks 71: 3 students (12, 30, 60) have marks less than 71. (3 * 100) / 4 = 75.
  Student with marks 30: 3 students (12) have marks less than 30. (1 * 100) / 4 = 75.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 10^5
0 <= Marks <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Student Percentile Calculation

Console