Calculate Special Bonus - Leetcode Solution

Problem statement:

Suppose a company has employees numbered from 1 to n. Each employee is assigned a profit value, p[i], where p[i] denotes the profit made by the ith employee. The company decides that it will pay a special bonus to its employees. The bonus will depend on the profit value of each employee and the rank of that employee in the list of profits. The employees with higher profits will receive a larger bonus than the ones with lower profits. Also, employees with the same profit will receive the same bonus, and the ranking will be in descending order of profits.

For example, if the profits are p = [10,20,30,40], then the bonus values will be [4,3,2,1], respectively.

Write a function that takes in two arguments: the number of employees, n, and an array of employee profits, p, and returns an array of bonus values for each employee.

Solution:

The solution to this problem involves sorting the employee profits in descending order, as the bonus distribution is based on the ranking of the profits. We will then assign ranks to each profit, based on their sorted position in the array. If two employees have the same profit, they will have the same rank and the same bonus value.

Once the ranks are assigned, we can calculate the bonus values using the formula (n - rank + 1).

The implementation of the above algorithm in Python is given below:

def calculate_bonus(n, p):
    # sort the profits in descending order
    sorted_p = sorted(p, reverse=True)
    # assign ranks to each profit
    ranks = {sorted_p[i]:i+1 for i in range(n)}
    # calculate bonus values for each employee
    bonus = [n - ranks[p[i]] + 1 for i in range(n)]
    return bonus

The function takes in two arguments, n and p, where n is the number of employees and p is an array of employee profits. We first sort the employee profits in descending order and then assign ranks to each profit using a dictionary. The ranks are assigned based on the sorted position of the profits in the array. The bonus values are then calculated using the formula given above and returned as an array.

Let's test the function with an example:

>>> p = [10, 20, 30, 40]
>>> calculate_bonus(4, p)
[4, 3, 2, 1]

The above output confirms that the function is working correctly.

Time Complexity Analysis:

The time complexity of the above solution is O(nlogn), where n is the number of employees. This is because the time taken to sort the employee profits dominates the algorithm's time complexity. The time complexity of the dictionary creation and calculating bonus values is O(n), which is less than the time taken to sort the profits. Therefore, the overall time complexity of the algorithm is O(nlogn).

1