algoadvance

Leetcode 453. Minimum Moves to Equal Array Elements

Problem Statement

You are given an integer array nums of size n. In one move, you can increment n - 1 elements of the array by 1. Your goal is to make all the elements in the array equal. Return the minimum number of moves required to make all the elements equal.

Clarifying Questions

  1. Can the array be empty?
    • No, the problem statement implies that there is at least one element in the array.
  2. Are there any constraints on the values of the elements in the array?
    • The problem does not explicitly mention constraints, but let’s assume the values can be any valid integers.
  3. What should we assume about the array size (n)?
    • The array size n can be any positive integer.

Strategy

When incrementing n - 1 elements by 1, it is equivalent to decrementing one element by 1 to match the other elements. Therefore, to find the total number of moves, we can calculate the total number of decrements needed such that all elements become equal to the minimum element in the array.

This leads to the following steps:

  1. Calculate the minimum element in the array.
  2. Compute the number of moves needed by summing the difference between each element and the minimum element.

Time Complexity

Code

public class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;

        // Find the minimum value in the array
        for (int num : nums) {
            if (num < min) {
                min = num;
            }
        }

        // Calculate the total number of moves
        for (int num : nums) {
            sum += num - min;
        }

        return sum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 3};
        System.out.println(solution.minMoves(nums));  // Output: 3

        nums = new int[]{1, 1, 1};
        System.out.println(solution.minMoves(nums));  // Output: 0
    }
}

This solution effectively and efficiently finds the minimum number of moves required to make all elements in the array equal by leveraging the observation that incrementing n - 1 elements is the same as decrementing one element each time until all elements equal the minimum element.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI