[LeetCode] 2033. Minimum Operations to Make a Uni-Value Grid (Python)

 

난이도: Medium

Problem Description

---

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

 

A uni-value grid is a grid where all the elements of it are equal.

 

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

 

 

Problem Example

---

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

 

Constraints

---

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= x, grid[i][j] <= 104

 

✏️ Solution

---

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        check = -1
        n = len(grid)
        m = len(grid[0])
        new_grid = []

        for i in range(n):
            for j in range(m):
                new_grid.append(grid[i][j])
                if check == -1:
                    check = grid[i][j] % x
                elif check != grid[i][j] % x:
                    return -1
        
        new_grid.sort()

        answer = 0
        target = new_grid[(n * m) // 2]
        for num in new_grid:
            answer += abs(target - num) // x

        return answer

먼저 조건을 만족하려면 grid에 있는 숫자들이 모두 x로 나누었을 때의 나머지가 같아야한다.

만약 하나라도 나머지가 다르다면 그 grid는 조건을 만족할 수 없기 때문에 -1을 반환하면된다.

 

모두 나머지가 같다면 이제 최소 연산 횟수를 구하면 된다.

 

이는 grid에 있는 모든 숫자들을 1d array로 만들어 정렬시켜주면 된다.

 

정렬 시킨 1d array의 중앙값을 찾아 target이라는 변수에 저장 시켜주었다.

 

이제 grid의 모든 숫자에 대해 abs(target - num) // x를 구해 모두 더해주면 최소 연산 횟수를 구할 수 있다.

 

이 문제는 알고리즘 적 문제보다는 수학 문제 푸는 듯한 느낌이 들었다.

 

⚙️ Runtime & Memory

---

 

 

---

문제: 2033. Minimum Operations to Make a Uni-Value Grid

 

깃허브: github

algorithmPractice/LeetCode/2160-minimum-operations-to-make-a-uni-value-grid at main · laewonJeong/algorithmPractice