DEV Community

Alkesh Ghorpade
Alkesh Ghorpade

Posted on • Originally published at alkeshghorpade.me

LeetCode - Minimum Operations to Make Array Equal

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/minimum-operations-to-make-array-equal

Example 1:

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 6
Output: 9
Enter fullscreen mode Exit fullscreen mode

Constraints:

- 1 <= n <= 10^4
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute Force

As per the problem statement, the value at index i in the array is equal to (2 * i) + 1. The array of size n can be represented as follows:

arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1,.... 2 * (n - 1) + 1]

when n = 6
arr = [2 * 0 + 1, 2 * 1 + 1, 2 * 2 + 1, 2 * 3 + 1, 2 * 4 + 1, 2 * 5 + 1]
    = [1, 3, 5, 7, 9, 11]

when n = 7
arr = [1, 3, 5, 7, 9, 11, 13]
Enter fullscreen mode Exit fullscreen mode

The array elements are ordered in a linear arithmetic series. Let's calculate the number of operations at each step.

arr = [1, 3, 5, 7, 9, 11, 13]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[6] = 13 by 1.
arr = [2, 3, 5, 7, 9, 11, 12]

We repeat the above process till arr[0] and arr[6] = 7

Number of operations = 6

Similarly, for arr[1] and arr[5], the number of operations to update value to 7 will be 4.
For arr[2] and arr[4], the number of operations will be 2.

Total number of operations = 6 + 4 + 2
                           = 12

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]

First operation, we will increase arr[0] = 1 by 1 and decrease arr[8] = 17 by 1.
arr = [2, 3, 5, 7, 9, 11, 13, 15, 16]

We repeat the above process till arr[0] and arr[8] = 9

Number of operations = 8

Similarly, for arr[1] and arr[7], the number of operations to update the value to 9 will be 6.
For arr[2] and arr[6], the number of operations will be 4.
For arr[3] and arr[5], the number of operations will be 2.

Total number of operations = 8 + 6 + 4 + 2
                           = 20
Enter fullscreen mode Exit fullscreen mode

From the above pattern, we observe at any step or index i, the number of operations is n - 2 * i - 1. The total number of operations will be

number_of_operations = 0

for(int i = 0; i < n / 2; i++) {
    number_of_operations += n - (2 * i) - 1
}

return number_of_operations
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(n), and the space complexity is O(1).

Efficient approach

We can further optimize the above approach. Let's observe the pattern for the number of operations. For every i = 0, 1, 2,...(n/2) - 1, we get the series as

n - 1, n - 3, n - 5,.......7, 5, 3, 1.
Enter fullscreen mode Exit fullscreen mode

This is an arithmetic series a, a + d, a + 2d...., where a = 1 and d = 2. The arithmetic sum of this series is

sum = n * (2 * a + (n - 1) * d) / 2
Enter fullscreen mode Exit fullscreen mode

In our case, n = n / 2. We apply the above formula

sum = (n / 2) * (2 * 1 + (n/2 - 1) * 2) / 2
    = n * (2 + (n - 2)) / 4
    = n * (n) / 4
    = (n * n) / 4
Enter fullscreen mode Exit fullscreen mode

When n is odd, the arithmetic series is n - 1, n - 3,....5, 3, 1. When n is even, the arithmetic series is n - 1,...6, 4, 2. We apply the same arithmetic series formula, reducing the sum to (n * n) / 4.

The time and space complexity of the above approach is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    int minOperations(int n) {
        return (n * n) >> 2;
    }
};
Enter fullscreen mode Exit fullscreen mode

Golang solution

func minOperations(n int) int {
    return (n * n) >> 2
}
Enter fullscreen mode Exit fullscreen mode

JavaScript solution

var minOperations = function(n) {
    return (n * n) >> 2;
};
Enter fullscreen mode Exit fullscreen mode

For n = 6, we return the solution as (6 * 6) >> 2 = 9.

Top comments (0)