Optimal Request Load Balancing BNY MELLON - IIT (BHU) Varanasi

Problem Preview

"**Mode:** On-Campus **Exam Pattern:** 2 coding + 1 debugging **OA Date:** 2026-11-11 ## Optimal Request Load Balancing Description You are managing a distributed system consisting of N servers, numbered from 1 to N, and M incoming requests. Each request i (1 <= i <= M) has a designated home server C[i] (1 <= C[i] <= N) where its data is cached. - If a request is processed by its home server, it takes 1 unit of time. - If a request is processed by any other server (a foreign server), it takes 2 units of time. Each server can process at most one request at a time, and it processes requests sequentially. All servers can operate simultaneously. Your goal is to find the minimum total time required to process all M requests if you distribute the load optimally across the N servers. Input Format - The first line contains two space-separated integers N (the number of servers) and M (the number of requests). - The second line contains M space-separated integers C[1], C[2], ..., C[M], where C[i] represents the home server ID for the i-th request. Output Format Print a single integer representing the minimum time required to process all requests. Constraints 1 <= N <= 10^5 1 <= M <= 2 * 10^5 1 <= C[i] <= N Sample Input 3 5 1 1 1 1 2 Sample Output 2 Explanation Server 1 is the home server for 4 requests. Server 2 is the home server for 1 request. Server 3 has no home requests. An optimal assignment is: - Server 1 processes 2 home requests in 2 units of time. - Server 2 processes 1 home request in 1 unit of time. - Server 3 processes 1 foreign request in 2 units of time. - Server 2 processes 1 additional foreign request, taking 2 units of time, for a total of 3 units. However, this assignment takes 3 units of time. The minimum possible time is 3 units. Correct Sample Output 3"