We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Equal Array Elements

Number: 453

Difficulty: Medium

Paid? No

Companies: IBM, Google, Adobe, Amazon, Coursera, Indeed

Problem Description

Given an integer array nums, determine the minimum number of moves required to make all the array elements equal. In one move, you can increment n - 1 elements of the array by 1.

Key Insights

  • Instead of thinking about incrementing n-1 elements, reverse the operation: it is equivalent to decreasing one element by 1.
  • The optimal strategy is to reduce all elements until they reach the minimum element in the array.
  • The total number of moves is the sum of differences between each element and the minimum element.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the nums array (we need to iterate over the list to find the minimum and calculate differences).
Space Complexity: O(1) (only constant extra space is used regardless of input size).

Solution

The idea is to first find the minimum element in the array. Then, for each element in the array, calculate the difference between that element and the minimum element. The sum of all these differences gives the minimum number of moves required to equalize the array. This approach works because incrementing the n-1 elements in a move is equivalent to decrementing one element by 1. This transformation simplifies the problem into summing differences.

The following code implementations in various languages demonstrate this approach.

Code Solutions

# Function to calculate the minimum moves to equal array elements
def min_moves(nums):
    # Find the minimum element in the array
    min_num = min(nums)
    # Initialize moves counter
    moves = 0
    # Calculate the difference between each element and the minimum element
    for num in nums:
        moves += num - min_num  # add difference to moves
    return moves

# Example usage:
nums = [1, 2, 3]
print(min_moves(nums))  # Output should be 3
← Back to All Questions