What if we are not smart enough to come up with decrease 1. Here is how we do it.


  • 19
    K

    First, the method of decreasing 1 instead of adding 1 for n-1 elements is brilliant. But, when I was doing the contest, I was dumb, so dumb to think outside the box. And this is how I tackled it using just math logic.

    First, traverse the array, get the sum and the minimum value. If every element is equal, then min*(len) should equal to sum. This part is easy to understand. So, if they are not equal, what should we do? we should keep adding 1 to the array for k times until min*(len)==sum. Then we have:

    len*(min+k)=sum+k*(len-1).
    ==> k=sum-min*len;

    Looks familiar? If you do it by decreasing 1 each time, this equation should be easy to understand!
    Some of you may have this question: how can I be sure that after adding 1 to (n-1) elements in the array, the minimum value is the previous min plus one. Is it possible that the minimum value stays the same after this? The answer is no, it's not possible. As long as all elements are not same, adding 1 to (n-1) elements meaning only one element in the array is not getting a candy. And I'm sure you will choose not to give the candy to the oldest one. So, yes, every time you do that add operation, the min value adds 1.

    public int minMoves(int[] nums) {
            if(nums==null||nums.length<=1) return 0;
            long min=(long)nums[0];
            long sum=0;
            for(int i=0;i<nums.length;i++){
                sum+=(long)nums[i];
                min=Math.min(min,nums[i]);
            }
            return (int)(sum-min*nums.length);
        }
    

  • 1
    B

    Is it possible that the minimum value stays the same after this? The answer is no, it's not possible. As long as all elements are not same, adding 1 to (n-1) elements meaning only one element in the array is not getting a candy. And I'm sure you will choose not to give the candy to the oldest one.

    Can you prove the above statement? It sounds like an assertion, not a provement.


  • 3
    K

    @BeaverNation Absolutely! It takes two steps to prove this. First, we need to prove min value has to increase by 1 for each move. Second, we need to prove that for each move, the max value, or one of the max values if there are more than one, should be the one stays the same.

    To prove the first: say, it takes K moves to reach all-equal state. Among these K moves, there are k1 moves that min value gets to increase by 1, and the other k2 moves it doesn't.
    K=k1+k2
    Then we can have:
    len*(min+k1)=sum+K*(len-1)
    ==> K-K*(len)+k1*(len)=sum-min*(len)
    ==> K-k2*(len)=sum-min*(len)
    ==> K=sum-min*(len)+k2*(len)
    In this problem, we need to return the minimum moves, which in this case, minimum value of K. So, to make K smallest, considering that sum, min and len are determined by input, we have to make sure k2 is the smallest, which is zero. Then we have: K=k1=sum-min*(len). Which means that to get minimum K, we have to increase min every round, and the minimum value of K is sum-min*(len).

    To prove the second: Since we have proved that it takes minimum moves of sum-min*(len) to reach equal state, and after the first traversal of the input array, we have min and max of the array. After calculation, we have equal-state value: min+sum-min*(len). So, do we really have to make max value, or one of the max values, stay the same? The answer is no, since we already know the final value, as long as each element doesn't exceed that, it doesn't matter which value, except the min value, stays the same for each move. Here's an example:
    Given [1,2,3], we can follow these steps to reach equal state: [1,2,3]==>[2,2,4]==>[3,3,4]==>[4,4,4]
    The reason of picking max value to be the one stays the same is to make sure the max value increases the minimum times so that it won't exceed the final value. It is not the only way to do it, but the easiest to come up with.

    Hope my answer satisfies you!


  • 0
    V

    @KnightY That's a good explanation !thank you


  • 0
    L

    very nice! easy for me to understand.


  • 0
    N
    public class Solution {
        public int minMoves(int[] a) {
         
            //incrementing n-1 elements to reach max is equivalent to
            //decrementing max elemnt by (max-min)) to reach the rest
            int count = 0;
            boolean proceed = true;
            while(proceed){
                int max = a[0];
                int min = a[0];
                int idx = 0;
                proceed = false;
                for(int i=1; i < a.length; i++){
                    if(max < a[i]){
                        max = a[i];
                        idx = i;
                        proceed = true;
                    }
                    if(a[i] < min){
                        min = a[i];
                    }
                }
                a[idx] -= (max-min);
                count += (max-min);
            }
            
            return count;
        }
    }
    

  • 0
    N

    Excellent explanation, this helped me a lot, thankyou so much!!.

    I read through the entire post and i could deduce the expression step by step :

    if all elements are equal, say all elements are represented by min, then sum of all elements is :
    len*min = sum

    Now, say all elements are not equal, in that case, we keep adding 1 to each element, until it reaches max value.
    say for ex : [1, 2, 3, 4]
    step 1: 1 + 1 ( first elem)
    step 2 : 2 + 1( first elem + 1)
    step 3..... so on

    hence left side expression becomes
    len*(min + k) = sum + k * (len - 1)
    lenmin + klen = sum + klen - k
    len
    min = sum - k
    k = sum - len*min


Log in to reply
 

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