Citadel OA Interview Question: Minimum Operations to Complete All Jobs

There are n jobs that can be executed in parallel on a processor, where the execution time of the i-th job is executionTime[i].

To speed up execution, the following strategy is used.

In one operation, a job is chosen as the major job and is executed for x seconds. All other jobs are executed for y seconds, where y < x.

A job is complete when it has been executed for at least executionTime[i] seconds, then it exits the pool.

Find the minimum number of operations in which the processor can completely execute all the jobs if run optimally.

Example

Consider n = 5, executionTime = [3, 4, 1, 7, 6], x = 4, and y = 2.

The following strategy is optimal using 1-based indexing.

• Choose job 4 as the major job and reduce the execution times of job 4 by x = 4 and of other jobs by y = 2.
  Now executionTime = [1, 2, -1, 3, 4]. Job 3 is complete, so it is removed.
• Choose job 4. Now executionTime = [-1, 0, -3, -1, 2]. Jobs 1, 2, and 4 are complete.
• Choose job 5. Now executionTime = [-, -, -, -, -2]. Job 5 is complete.

It takes 3 operations to execute all the jobs, so the answer is 3.

Function Description

Complete the function getMinimumOperations in the editor below.

getMinimumOperations has the following parameters:

• INTEGER_ARRAY executionTime
• INTEGER x
• INTEGER y

Returns

INTEGER: the minimum number of operations in which the processor can complete the jobs

Constraints

• 1 <= n <= 10^5
• 1 <= executionTime[i] <= 10^9
• 1 <= y < x <= 10^9

Sample Input 0

5
3
3
6
3
9
3
2

Sample Output 0

3

Explanation 0

• Choose job 5, then executionTime = [1, 1, 4, 1, 6]. All jobs are still in the pool.
• Choose job 5, then executionTime = [-1, -1, 2, -1, 3]. Jobs 1, 2, and 4 are complete.
• Choose job 5, then executionTime = [-, -, 0, -, 0]. Jobs 3 and 5 are complete.

It takes 3 operations to execute all the jobs.

The core idea is to treat each operation as a uniform baseline reduction of y for every job, plus an extra reduction of x – y for the chosen major job. If we guess that the processor runs for k operations, then every job receives k * y seconds of progress automatically, and the remaining gap tells us how many times that job must still be chosen as the major job. This leads to a standard binary search on the answer: for a candidate k, compute the total extra major-job selections needed across all jobs using integer division, and verify whether that total is at most k. The problem is therefore solved efficiently with a monotonic feasibility check, making it suitable for large n.