Katkat
Back

Fewest Increment-All-but-One Moves to Make Array Values Equal

SquarepointData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

From a Squarepoint technical screen: one move adds 1 to every element of an integer array except one chosen element, and you must find the fewest moves that make all elements equal. It tests reasoning about what each move really changes, along with negative values and answers beyond the 32-bit range.

You are given an integer array nums. In one move, you choose one element and leave it unchanged while adding 1 to every other element. Return the minimum number of moves needed to make all elements equal.

Function Signature

def min_moves_to_equal(nums: list[int]) -> int:

Rules

  • Each move adds exactly 1 to every element except the one chosen.
  • The chosen element can be different from one move to the next.
  • An array whose elements are already all equal, including a single-element array, needs 0 moves.

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • The answer can reach about 2 * 10^14, which exceeds the 32-bit signed range but stays below 2^53.

Examples

Example 1

Input: nums = [1, 3]
Output: 2

Keep 3 unchanged twice: [1, 3] becomes [2, 3] and then [3, 3].

Example 2

Input: nums = [4, 1, 6]
Output: 8

Example 3

Input: nums = [-2, 5, -2, 0]
Output: 9