c# solution


  • 0
    C
    public int MinMoves(int[] nums) 
    {
        int min = nums.Min();
        return nums.Sum(n => n - min);
    }
    

  • 0
    M

    Here I implement the solution in a single iteration of the array:

    I can't compete with cpp0x's beautifully succinct solution in terms of lines of code; however, if you are interested in a detailed explanation, you're welcome to have a look at this.

        public int MinMoves(int[] nums) {
            /* Because this problem as to do with the relative difference between numbers the following are logically equivalent:
             * 1) Increase everything EXCEPT the given item by one
             * 2) Decrease the GIVEN item by one
             *
             * Of course, the second expression is much more efficient. This is the first level of optimization.
             * 
             * Now that the objective has become to reducing a single item to zero, we can add a second level of optimization: 
             * This is done by deducing that, instead of decreasing the number by 1 iteratively, we can simply sum the differences
             * between each item and the minimum item. (You can test this empirical quite simply.)
             *
             * The third level of optimization involves doing this all in one iteration of the array:
             * 1) Assume the first item is the minimum; then move to the next item.
             * 2) If a smaller minimum is found, then retrospectively add the difference between the assumed minimum and 
             *    the new minimum for all the items already parsed.
             *    (This can be done rather easilly by multiplying the difference between the old minimum and new minimum by 
             *     the number of items already parsed.)
             */
            
            int noOfIterations = 0;
            int min = nums[0];
            
            // O(n) implementation:
            for (int i = 1; i < nums.Length; i++)   // Ignore the first element.
            {
                if (nums[i] >= min)
                {
                    // Add the difference between this item and the minimum. 
                    noOfIterations += nums[i] - min;
                }
                else
                {
                    // If we find a smaller minimum, we need to pretend that we had substracted the difference all along
                    // (by multiplying the difference in the minimums by the number of items we have processed already).
                    noOfIterations += ((min - nums[i]) * i);
                    min = nums[i];
                }
            }
            return noOfIterations;
        }
    

Log in to reply
 

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