c# solution

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

  • 0

    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;
                    // 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.