Leetcode Array Challenge: Time to Equality Solution Guide

Problem Description

You have an integer array A with N elements. In one second, you can bump up the value of one element by 1.

Figure out the least amount of time in seconds to make all the elements in the array the same.

Problem Constraints

1 <= N <= 1000000

1 <= A[i] <= 1000

Input Format

First argument is an integer array A.

Output Format

Return an integer denoting the minimum time to make all elements equal.

Example Input

A = [2, 4, 1, 3, 2]

Example Output

8
Example Explanation

We can change the array A = [4, 4, 4, 4, 4]. The time required will be 8 seconds.

Solution

public class Solution {
    public int solve(int[] A) {

        int maxElement = Integer.MIN_VALUE;
        int sumOfElement = 0;
        for(int i=0;i<A.length;i++){
            sumOfElement = sumOfElement + A[i];
            if(A[i]>maxElement){
                maxElement = A[i];
            }
        }

        return (maxElement*A.length) - sumOfElement;

    }
}

Code Explanation

1. Initialize Variables:

    int maxElement = Integer.MIN_VALUE;
    int sumOfElement = 0;
   

   • maxElement: This variable is initially set to the smallest possible integer value (Integer.MIN_VALUE). The idea here is to find the largest number in the array.

   • sumOfElement: This variable will store the sum of all elements in the array.

2. Loop Through the Array:

    for(int i=0; i<A.length; i++) {
        sumOfElement = sumOfElement + A[i];
        if(A[i] > maxElement) {
            maxElement = A[i];
        }
    }
   

   • Summing Elements: As you go through each element in the array, you keep adding it to sumOfElement. This gives you the total sum of all elements in the array.

   • Finding the Maximum Element: At the same time, you compare each element to maxElement. If the current element is larger than maxElement, you update maxElement to this value. By the end of the loop, maxElement will hold the largest value in the array.

3. Calculate the Result:

    return (maxElement * A.length) - sumOfElement;
   

   • Concept:

     • The idea is that you want all elements in the array to be as large as the maximum element (maxElement).

     • If every element were already equal to maxElement, the total sum of the array would be maxElement * A.length (because each element would be maxElement and there are A.length elements).

     • However, since the elements are not all maxElement, you subtract the actual sum of the array (sumOfElement) from this ideal sum.

   • Final Result: The difference between this "ideal" sum and the actual sum gives you the total number of increments (or seconds) needed to make all elements equal to maxElement.

Example to Illustrate:

Suppose A = [1, 3, 4, 1].

• Step 1: Find the biggest element, which is 4.

• Step 2: Add up all the elements: 1 + 3 + 4 + 1 = 9.

• Step 3: Imagine if all elements were 4: 4 * 4 = 16.

• Step 4: The difference is 16 - 9 = 7.

So, the minimum time needed to make all elements in A equal by increasing them one by one is 7 seconds.

Summary

The code figures out how many steps (or seconds) it takes to make all the elements in an array the same. It does this by calculating the difference between the sum of an ideal array (where every element is the maximum value) and the actual sum of the array. This difference tells us the minimum time needed to make all the elements equal.