2033. Minimum-Operations-To-Make-A-Uni-Value-Grid

After reading this question, its easy to see that this task is impossible if all the numbers are not equal mod x. The next thing we would need to consider is to find which number we should make all the numbers equal to in order to get the minimum number of operations.

For me, there were two possible candidates for the number:

• the median of the numbers
• the number closest to half the range

Consider the case [1, 2, 3, 4, 10] and x = 1: Taking the median of the numbers, we get 3 and the number closest to half the range is 4. We check how many operations it takes to achieve the task for each candidate:

• If we pick 3 as the number, 11 ([+2, +1, 0, -1, -7]) operations would be needed to make all the numbers equal.
• If we pick 4 as the number, 12 ([+3, +2, +1, 0, -6]) operations would be needed to make all the numbers equal.

Therefore, taking the median candidate is the better choice. We can grab the median of the numbers by sorting it and getting the middle (n // 2) element. Then we take the difference between the median and each number divided by x and sum them up to get the result.

class Solution(object):
    def minOperations(self, grid, x):
        """
        :type grid: List[List[int]]
        :type x: int
        :rtype: int
        """
        num_list = []
        remainder = grid[0][0] % x
        for row in grid:
            for num in row:
                if num % x != remainder:
                    return -1
                num_list.append(num) 

        n = len(num_list)
        num_list.sort()
        res = 0
        median = num_list[n // 2]
        for i in num_list:
            res += abs(median - i) // x

        return res

Time Complexity: O(mn log mn)

Space Complexity: O(mn)