Java O(n) solution. Short.


  • 110
    K

    Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.
    So, best way to do this is make all the elements in the array equal to the min element.
    sum(array) - n * minimum

    public class Solution {
        public int minMoves(int[] nums) {
            if (nums.length == 0) return 0;
            int min = nums[0];
            for (int n : nums) min = Math.min(min, n);
            int res = 0;
            for (int n : nums) res += n - min;
            return res;
        }
    }
    

  • 2
    M

    Can you prove why this is correct?
    Since if you keep adding 1 to n - 1 elements, the final answer may not be the max element in the original array. So when you substract 1 on 1 element, why the final answer is the min element in the original array?
    And why in these two situations steps are same?


  • 6
    H

    Thanks for your explanation of this question!
    According to your method, this is another implementation, just slightly difference in details:

    public int minMoves(int[] nums) {
        
        int result = 0;
        int min = nums[0];
        
        for (int i = 1; i < nums.length; i++)
        {
            if (nums[i] >= min)
                result += nums[i] - min;
            else
            {
                result += (min - nums[i]) * i;
                min = nums[i];
            }
        }
        return result;
    }

  • 4
    S

    @marcusgao94 Because you only care about the difference between elements instead of the final value. In the perspective of difference, add one to all the other elements is equivalent to subtract one from current element.


  • 13
    C

    Why are you so smart.


  • 25
    D

    @marcusgao94
    substract 1 on the max value, then add 1 on each element. this is the same as adding 1 to n - 1 elements. cool idea!

    my prove is based on solving equations:

    sum(array)+m*(n-1)=n*f
    f-min(array)=m

    where m is min moves to take, f is the final value of the array elements. the first equation means, by adding n-1 ones for m times, we will have n array elements with value f. the second equation means, the min value always add 1 in each move (because it's always the min value of all elements)
    solve the equations we have: m=sum(array)-n*min(array)


  • 0
    R
    This post is deleted!

  • 0
    S

    @dalerambo
    Thanks for ur equation, help a lot.


  • 0

    @HungryOrc same here, C#

        public int MinMoves(int[] nums) 
        {
            int min = nums[0];
            int moves = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] < min)
                {
                    moves += (min - nums[i]) * i;
                    min = nums[i];
                }
                else
                {
                    moves += nums[i] - min;
                }
            }
            
            return moves;
        }
    

  • 8
    S

    Great solution. Share my even shorter code:

    public int minMoves(int[] nums) {
    	int min = Integer.MAX_VALUE, sum = 0;
    	for (int n : nums) {min = Math.min(min, n); sum += n;}
    	return sum - nums.length * min;
    }
    

  • 0

    @shone only thing to consider here is possible integer overflow with summing up the whole array.


  • 0
    Y

    Could you please explain the reason?


  • 1
    S

    @jdrogin Thanks for the advice, but I think it's fine. My code may overflow in the middle of the process. However, the final result will still be correct if the return value doesn't overflow. Think about this: int a = Integer.MAX_VALUE + 1; a--;, variable a overflows in the first expression, but the final value is still correct.


  • 0

    @shone Indeed you are correct, thanks for pointing that out. I took a closer look at this case to see your point.

    int.Max + int.Max overflows to -2
    

    if you have in your input

    [int.Max, int.Max, 1] sum = -1
    

    your return will be

     -1 - (3 x 1) = -4
    

    In the end this will work out because as your sum overflows your number of moves overflows as well

    (int.Max - 1) + (int.Max - 1) = (int.Max + int.Max) - 2 = -2 - 2 = -4
    

    of course -4 is not the answer that makes sense but it is the answer that is correct given the overflow.


  • 0
    A

    Super smart solution. How am I to think of this in an interview?


  • -1
      public int minMoves(int[] nums) {
        int res = 0, min = Integer.MAX_VALUE;
        for(int n: nums) min = Math.min(min, n);
        for(int n: nums) res += n - min;
        return res;
      }

  • 0
    V
    This post is deleted!

  • 0
    W
    This post is deleted!

  • 0

    so smart solution!


  • 0
    A

    @dalerambo nice explanations!


Log in to reply
 

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