leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2033.cpp (744B)

      1 class Solution {
      2   public:
      3     int minOperations(const vector<vector<int>> &grid, int x) const {
      4         static int dp[100001];
      5         vector<int> vec;
      6 
      7         for (const auto &row : grid)
      8             vec.insert(end(vec), begin(row), end(row));
      9         sort(begin(vec), end(vec));
     10 
     11         for (int i = 0, acc = 0; i < size(vec) - 1; i++) {
     12             const int crnt = vec[i + 1] - vec[i];
     13             if (crnt % x) return -1;
     14             dp[i + 1] = acc += (i + 1) * crnt;
     15         }
     16 
     17         int res = INT_MAX;
     18         for (int i = size(vec) - 1, acc = 0; i > 0; i--) {
     19             acc += (size(vec) - i) * (vec[i] - vec[i - 1]);
     20             res = min(res, acc + dp[i - 1]);
     21         }
     22 
     23         return res != INT_MAX ? res / x : 0;
     24     }
     25 };