It is a math question


  • 129
    W

    let's define sum as the sum of all the numbers, before any moves; minNum as the min number int the list; n is the length of the list;

    After, say m moves, we get all the numbers as x , and we will get the following equation

     sum + m * (n - 1) = x * n
    

    and actually,

      x = minNum + m
    

    and finally, we will get

      sum - minNum * n = m
    

    So, it is clear and easy now.


  • 4

    Can you please explain why x = minNum + m?


  • 8
    K

    @StefanPochmann before all elements reach to the same value, every time (n-1) elements add one meaning only one element remains the same, which of cause should be the max value( should be different from min value, otherwise they have reached the same value) of the array. So, with that being said, every time doing add one for (n-1) operation, the min value +1. If it takes m moves to reach x, then x=minNum+m. Also, I have a similar post, my post, you can take a look if you are still interested.


  • 0
    G

    @KnightY How to prove m is minimum?


  • 3
    K

    @guohua As long as min not equals to max, you keep doing add 1 to (n-1) elements, then min value for sure +1, I believe you understand this part already. So, I suppose your question is what if m moves means min value once equals to max and somehow this array adds 1 to (n-1) elements which makes it to go for another round to have all equal elements. If you think carefully, you will find out that by doing this, there exists a single add-1-operation that min value doesn't get to +1.

    So, if you want to get the second minimum moves to reach to all equal state, then you can have these equations instead:(I am using OP's equations so I think you can better understand and compare the differences)

    for second minimum m moves:

    sum+m*(n-1)=x * n

    x=minNum+m-1 (there is a single time min value doesn't +1)

    sum-minNum * n+n=m (m gets n moves more compared to the minimum value, because it also means you need to decrease every element by 1 after it reaches to the first equality, easy to understand, right?)


  • 0

    @wang.senyuan great explanation!!


  • 0
    S

    great idea, thank a lot


  • 11
    S

    Let me explain why x = minNum + m
    our goal is :increment minNum to be equal to maxNum

    • No matter how many add operations are executed,the goal won't change.
    • Every time we do the add operation,the min number in the array must participate in.
    • After an add operation,the minNum is still the min number
      So the minNum participate in every add operation
      So x = minNum + m

  • 0
    W

    thanks for sharing


  • 0
    M
    This post is deleted!

  • 0
    E
    This post is deleted!

  • 2
    E

    @StefanPochmann Here is what I think:
    Since the ADD is linear, every moves are exchangeable. So if we have one move that doesn't add 1 to the very beginningminNum, it means we didn't add 1 to the minNum at the first move, which is obviously not a good choice.


  • 0
    This post is deleted!

  • 0
    A

    @shijungg Thanks this helped me!


  • 0
    G

    Absolutely clear! Thank you.


  • 0
    M

    Thanks a lot for helping me recall some basic math method.


  • 0
    Y

    great explanation.I guess there are regular patterns,just can't figure out.Thanks


  • 0
    F

    @StefanPochmann Let me explain

    x <= minNum+m, as minNum can increase at most m times.
    m*(n-1) = sum-x*n >= sum-(minNum+m)n
    m
    (n-1) >= sum-(minNum+m)*n
    m <= sum-(minNum)*n
    so max value of m is sum-(minNum)*n, where minNum increase just m times and x = minNum+m

    Nextly, we need to prove just applying sum-(minNum)n times n-1 add operation can get all values equal, as we need to meet the goal.
    Obviously, we can do it.
    You can imagine that for every value you do num[i]-minNum times decrease 1 operation, totally, you do sum-minNum
    n times decrease 1 operation and the final value is minNum.
    Or you do num[i]-minNum times add operation for other n-1 numbers, finally, you can make all numbers equal with sum-(minNum)*n+minNum;


  • 1

    Thanks for sharing!
    C# version by your idea, time complexity O(n).

        public int MinMoves(int[] nums) {
            if(nums.Length < 2) return 0;
            int min=Int32.MaxValue;
            int sum=0;
            foreach(int item in nums)
            {
                sum+=item;
                min=Math.Min(min,item);
            }
            return sum-min*nums.Length;
        }
    

    And here's my own solution, time complexity O(nlogn) .. :(

        public int MinMoves(int[] nums) {
            if(nums.Length < 2) return 0;
            Array.Sort(nums);
            int endi = nums.Length - 1;
            int total = 0;
            while(nums[endi] != nums[0])
            {
                int cur =nums[endi] - nums[0];
                total += cur;
                nums[0] += cur;
                endi--;
                nums[endi] += total;
            }
            return total;
        }

  • 1
    Y

    Actually, this problem could be solved by dynamic programming:
    sort(nums)
    let s = move(nums, 0:k)
    then move(nums, 0:k+1) = s + abs(nums[k+1] - nums[k])
    return sum(s)

    In the end, you will find that this could written as sum(nums) - N * min;


Log in to reply
 

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