My thought on this problem


  • 0
    L

    The way I approached this problem was basically starting from the end.

    The ending condition is to have an array of equal numbers, call that n. Namely, [n,n,...,n] with t of n's.

    Now, consider moving one step back. Since only one element is not altered in this operation, wlog, put it at the far end (ordered array).

    This leads to: [n-k1,...,n-k1,n] where k1 is the number of moves applied to t-1 elements.

    Further step shows that now array is: [n-k1-k2, ..., n-k1-k2, n-k2, n-k1], assuming k1 < k2. Notice that the first t-2 terms are all the same.

    In fact, this can go on for t distinct moves, which leaves the array with:

    [n-\sum_{i=1}^{t}k_i, n-\sum_{i=1, i \ne j}^{t}k_i \forall j \in [1,t]]

    This array shows that the first element is n-sum of ki's, call that minimum value - min.

    And all the rest of the elements one extra kj, which is min+kj for j in [1,t]

    This proof might be a bit sloppy here, but it basically shows that you find the min first, and then find difference between that element and all the rest elements will give you all ki's, and the sum of ki is the total number of moves you made to the initial array.


Log in to reply
 

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