Leetcode 1551. Minimum Operations to Make Array Equal— Graphically Explained Python3 Solution

Photo by CDC on Unsplash

Problem Description

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

Input: n = 4
Output: 4
Explanation: arr = [1, 3, 5, 7]
First 3 operations choose x = 3 and y = 0, this leads arr to be [4, 3, 5, 4]
Now take 1 operation choose x = 2 and y = 1, thus arr = [4, 4, 4, 4].

Example 2:

Input: n = 7
Output: 12

Solution

BTW, don’t be frightened by the word “minimum” :)

To start with, just use a simple example like [1,3,5] (where n=3).

As the below picture shows, when n=3, the quickest way to make all elements equal is to

1. increase array[0] by 1 and decrease array[2] by 1
2. repeat #1

So the minimum operation is 2. This is not strict prove and the philosophy behind is to make all values increase/decrease towards the median value since, in each operation, I will have one value increase by 1 and the other decrease by 1, it will be natural to do that against mirrored elements in each end.

Now, look at other examples shown above like n=4 and 6. Mirrored elements will be taken by operations in X times where X=1,3,5,…, n/2 if n % 2 == 0. For n % 2 ==1, X will be 2,4,6,…,n-1.

OK, so the number of operations is the sum of an array

1,3,5,…, n/2 if n % 2 == 0

2,4,6,…,n-1 if n % 2 == 1

This is basically a math question now. The sum of an array like below is (start + end) * size_of_array / 2 = (start + start + size_of_array * 2–2) * size_of_array / 2 = (start + size_of_array -1) * size_of_array

start, start +2, start +4, …, end

Translating above illustration will lead to:

Time & Space Complexity

Since I just put n in a formula to calculate the end result, the time complexity is O(1) meaning no matter how n gets change (for example, from 10 to 100 or to 1000000), the run time will not grow along with it.

Space complexity will be O(1) as well since no extra space(like an auxiliary array) is used.

Extended Reading

Python3 cheatsheet:

https://medium.com/@edward.zhou/python3-cheatsheet-continuously-updated-66d652115549