{"id":8630,"date":"2021-10-21T21:23:04","date_gmt":"2021-10-22T04:23:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8630"},"modified":"2021-10-21T21:23:05","modified_gmt":"2021-10-22T04:23:05","slug":"leetcode-2033-minimum-operations-to-make-a-uni-value-grid","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-2033-minimum-operations-to-make-a-uni-value-grid\/","title":{"rendered":"LeetCode 2033. Minimum Operations to Make a Uni-Value Grid"},"content":{"rendered":"\n

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

A uni-value grid<\/strong> is a grid where all the elements of it are equal.<\/p>\n\n\n\n

Return the minimum<\/strong> number of operations to make the grid uni-value<\/strong><\/em>. If it is not possible, return -1<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[2,4],[6,8]], x = 2\nOutput:<\/strong> 4\nExplanation:<\/strong> We can make every element equal to 4 by doing the following: \n- Add x to 2 once.\n- Subtract x from 6 once.\n- Subtract x from 8 twice.\nA total of 4 operations were used.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[1,5],[2,3]], x = 1\nOutput:<\/strong> 5\nExplanation:<\/strong> We can make every element equal to 3.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> grid = [[1,2],[3,4]], x = 2\nOutput:<\/strong> -1\nExplanation:<\/strong> It is impossible to make every element equal.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == grid.length<\/code><\/li>
  • n == grid[i].length<\/code><\/li>
  • 1 <= m, n <= 105<\/sup><\/code><\/li>
  • 1 <= m * n <= 105<\/sup><\/code><\/li>
  • 1 <= x, grid[i][j] <= 104<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Median<\/strong><\/h2>\n\n\n\n
    To achieve minimum operations, the uni-value must be the median of the array.<\/p>\n\n\n\n
    Time complexity: O(m*n)
    Space complexity: O(m*n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author; Huahua\nclass Solution {\npublic:\n  int minOperations(vector>& grid, int x) {\n    const int mn = grid.size() * grid[0].size();    \n    vector nums;\n    nums.reserve(mn);\n    for (const auto& row : grid)\n      nums.insert(end(nums), begin(row), end(row));\n    nth_element(begin(nums), begin(nums) + mn \/ 2, end(nums));\n    const int median = nums[mn \/ 2];\n    int ans = 0;\n    for (int v : nums) {\n      if (abs(v - median) % x) return -1;\n      ans += abs(v - median) \/ x;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,11,177],"class_list":["post-8630","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-median","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8630","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8630"}],"version-history":[{"count":1,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8630\/revisions"}],"predecessor-version":[{"id":8631,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8630\/revisions\/8631"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8630"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8630"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8630"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}