Minimize Circular Redistribution Cost

Problem Statement

You are given an array of integers servers representing the current load on n servers arranged in a circle. You are also given an integer k, representing a batch of additional load that must be distributed across the servers.

Distribution starts at index start_index and proceeds clockwise. For each unit of load, you increment the value at the current index and then move to the next index (wrapping around to index 0 if you reach n-1). You must perform this until all k units of load are distributed.

Your task is to return the final state of the servers array after all k units have been distributed.

Function Signature

def distribute_load(servers: List[int], k: int, start_index: int) -> List[int]:

Constraints

• n (number of servers) is between 1 and 10^5.
• k is between 0 and 10^18.
• servers[i] is between 0 and 10^9.

Examples

Example 1:

• Input: servers = [1, 2, 3], k = 4, start_index = 1
• Distribution:
  1. Index 1: [1, 3, 3]
  2. Index 2: [1, 3, 4]
  3. Index 0: [2, 3, 4]
  4. Index 1: [2, 4, 4]
• Output: [2, 4, 4]

Example 2:

• Input: servers = [0, 0], k = 5, start_index = 0
• Output: [3, 2]

Edge Cases

• k is much larger than the sum of n. Use division to optimize cycles.
• k = 0 or empty array.