A survey company operates a fleet of n drones parked together at a shared charging dock, each holding a whole-number battery level. Every charging cycle, a technician pulls exactly one drone aside for a routine firmware check -- that drone's battery stays exactly where it is for the cycle -- while every other drone on the dock receives exactly one extra unit of charge. The technician is free to choose a different drone to exclude on each cycle, and wants every drone's battery level to become identical using as few charging cycles as possible.
Given the starting battery levels, determine the minimum number of charging cycles required.
The first line contains a single integer n, the number of drones. The second line contains n space-separated integers a_1, ..., a_n, the starting battery level of each drone.
Print a single integer: the minimum number of charging cycles needed so that all drones end up with equal battery levels. This value can exceed what a 32-bit integer can hold, so use a 64-bit (or arbitrary-precision) integer type.
Example 1
Input
3 1 2 3
Expected
3
Explanation
Battery levels are [1,2,3]. Excluding a drone from a cycle is equivalent to letting the other drones catch up to it, so the minimum number of cycles equals how far every drone must rise relative to the lowest starting drone: (1-1)+(2-1)+(3-1) = 0+1+2 = 3. Answer: 3.
Example 2
Input
2 5 9
Expected
4
Explanation
With only two drones, excluding one drone each cycle simply means the other drone gets +1 charge. Bringing the drone at 5 up to the drone at 9 takes exactly 9 - 5 = 4 cycles (always exclude the drone that already reads 9). Answer: 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →