Simple one-liners


  • 60

    Incrementing all but one is equivalent to decrementing that one. So let's do that instead. How many single-element decrements to make all equal? No point to decrementing below the current minimum, so how many single-element decrements to make all equal to the current minimum? Just take the difference from what we currently have (the sum) to what we want (n times the minimum).

    Python:

    def minMoves(self, nums):
        return sum(nums) - len(nums) * min(nums)
    

    Ruby:

    def min_moves(nums)
      nums.inject(:+) - nums.size * nums.min
    end
    

    Java (ugh :-):

    public int minMoves(int[] nums) {
        return IntStream.of(nums).sum() - nums.length * IntStream.of(nums).min().getAsInt();
    }
    

    C++ (more ugh):

    int minMoves(vector<int>& nums) {
        return accumulate(begin(nums), end(nums), 0L) - nums.size() * *min_element(begin(nums), end(nums));
    }
    

    (edit: I changed 0 to 0L because it failed the apparently added testcase [1,2147483647])


  • 0
    K

    @StefanPochmann Nice solution. I think C++ is not more ugh because think about a situation if you had to do min or sum operation on subarray. Other langauges syntax would be ugh then :D


  • 0

    @kaidul Well, that's not the situation we have here. And I'm not saying it's more ugh in general, I'm only comparing my solutions. Anyway, in Python and Ruby you have nice slicing syntax, so it would just be like min(nums[i:j]) or nums[i..j].min. That's not ugh at all. Looks like in Java I'd have to add .skip(i).limit(j). Oh well...


  • 2

    Same idea using Python's reduce. Sub m for min in return statement for 1-liner but there's TLE on large input.

    m = min(nums)
    return reduce(lambda x, y: x + y - m, nums, 0)
    

  • 1
    D

    Nice explanation! I thought about incrementing all and decrementing one of them and brute forced, but that exceeded the memory limit and I was stuck there...


  • 0
    T

    JavaScript version

    var minMoves = function (nums) {
        return eval(nums.join('+')) - nums.length * Math.min(...nums);
    };
    

    note: eval is not suggested for using.
    eval free version

    var minMoves = function (nums) {
        return nums.reduce((a, b) =>a + b) - nums.length * Math.min(...nums);
    };
    

  • 0
    L

    What if the interviewer turns around and tells you to print each step? How would you modify your solution?


  • 1
    T

    @lekzeey
    Hope you can understand JavaScript

    var minMoves = function (nums) {
        // find min
        const min = Math.min(...nums);
        // copy a new array from nums
        let step = nums.slice();
    
        nums.forEach((value, index)=> {
            let diff = value - min;
            while (diff-- > 0) {
                // add every number by one except current index
                step = step.map((v, i)=>i === index ? v : v + 1);
                // print every step
                console.log(step.join(' '));
            }
    
        });
    };
    

  • 0

  • 0
    L

    @troy351 thanks this is exactly what i was looking for
    @ahendy thanks but not quite what I was looking for. This is just a longer version of stefan's solution


  • 1

    Thanks. You teach me more about program than any of my professors.


  • 0
    K

    One liners are great and all, but this solution has the flaw that it can easily overflow if the numbers in the array are large.


  • 0
    T

    @kurlak
    Did you mean sum(nums[i] - min) is better than sum(nums) - len * min?


  • 0
    K

    @troy351: Yes, that's what I'm getting at.


  • 0

    @kurlak But that's Python, and Python's ints grow arbitrarily large, there's no overflow. Same with Ruby. And I think Java is safe because it might overflow but then overflow right back to the correct end result (because int operations are defined to be like modulo 232 (in the range -231 to 231-1)). C++ as far as I know leaves overflow behavior undefined but common implementations do behave like Java. But if you can provide an input where any of my solutions fail, I'd be quite interested.


  • 0
    C

    @troy351
    sum(nums) may bigger than Integer.MAX_VALUE


  • 0

    You know so many advanced functions in those languages, which is pretty amazing.

    However, to practice algorithm in LeetCode, I prefer my code below, 1 loop.

    public int minMoves(int[] nums) {
            int n = nums.length, min = 0, count = 0, actualMin = nums[0];
            for (int num : nums) {
                count += num - min;
                if (num < actualMin) 
                    actualMin = num;
            }
            count -= actualMin * n;
            return count;
        }
    

  • 0
    C

    wow! the sum idea is brilliant!


  • 0
    L

    I am using the C++ solution:

    int minMoves(vector<int>& nums) {
        if(nums.size()==1)
            return 0;
        return accumulate(begin(nums), end(nums), 0) - nums.size()**min_element(begin(nums), end(nums));
    
    }
    

    , but why I got a run time error when the input is [1,2147483647] ?

    Thanks~


  • 0

    @lusha Mine failed that as well now, I guess that testcase was added later. Apparently accumulate doesn't like the overflow, so I changed the 0 to 0l to prevent that and now it gets accepted again.


Log in to reply
 

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