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