Algorithm to Make a List Equal with Increments

You are given a list of integers nums, and want to make the values equal. Consider an operation where you pick an integer in the list and increment every other value .

Return the minimum number of operations required to make integer values equal.

Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 4]
Output
5
Explanation
Here are the operations we can use:
[2, 4, 4]
[3, 5, 4]
[4, 5, 5]
[5, 6, 5]
[6, 6, 6]

Hints:
Increasing all other elements except the largest element is similar to decreasing only the largest element.

List Equality Algorithm with Increments

The number of operations won’t change if we decrement the only largest element. We can simulate the process by first sorting the numbers in the non-ascending order. Then we can count the difference between two numbers, but we need to maintain a counter of those numbers that we have decremented. For example, [4 3 1], then [3 3 1], then if we bring 3 to 1, the total cost is (3-1)*2 as we have two 3’s.

1
2
3
4
5
6
7
8
9

class Solution:
    def makeListEquality(self, nums):
        nums.sort(reverse=True)
        ans = 0
        cnt = 1
        for i in range(len(nums) - 1):
            ans = ans + (nums[i] - nums[i + 1]) * cnt
            cnt += 1
        return ans

class Solution:
    def makeListEquality(self, nums):
        nums.sort(reverse=True)
        ans = 0
        cnt = 1
        for i in range(len(nums) - 1):
            ans = ans + (nums[i] - nums[i + 1]) * cnt
            cnt += 1
        return ans

Because of using sorting algorithm, the time complexity is O(NLogN). We can do this in linear time instead. Because for each number, we eventually need the (x-min) to bring it down. Thus, we need to compute the minimal and accumulate each difference.

1
2
3
4
5
6
7

class Solution:
    def makeListEquality(self, nums):
        m = min(nums)
        ans = 0
        for i in nums:
            ans += i - m
        return ans

class Solution:
    def makeListEquality(self, nums):
        m = min(nums)
        ans = 0
        for i in nums:
            ans += i - m
        return ans

–EOF (The Ultimate Computing & Technology Blog) —