3-line C++ solution: ans = sum - n*min with clear thinking process and proof (equivalent to decrement one value)


  • 0

    For any given array {xi=1:N}, the answer is simply Σi=1:N xi=1:N - N*xmin, where xmin is the min of the array.

    Proof: it is clearly that the solution to this problem only depends on the relative differences between entries of {xi=1:N}, i.e.,

    • Solution to array {xi=1:N} is same as solution to {xi=1:N + C}, where C is arbitrary constant.

    Therefore, incrementing N-1 entries by 1 is equivalent to decrementing the left over entry by 1. So the answer will be how many decrements it takes to decrease all xi=1:N to a same value. Apparently, the minimum is to decrease every entry to xmin, so

    • ans = Σi=1:N (xi=1:N - xmin) = Σi=1:N xi=1:N - N*xmin.
        int minMoves(vector<int>& nums) {
          int minx = INT_MAX, sum = 0;
          for (int x:nums) { sum += x; minx = min(minx, x); }
          return sum - minx*nums.size();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.