Very simple Java O(n) solution with explaination in the comment


  • 0
    J

    '''

    public int findMinMoves(int[] machines) {
        if ((machines == null) || (machines.length <= 1)) return 0;
        long sum = 0;
        for (final int machine : machines) sum += machine;
        if ((sum % machines.length) != 0) return -1;
        final int avg = (int)(sum / machines.length);
        if (machines.length == 2) return Math.max(machines[0], machines[1]) - avg;
        
        /*
         * The main idea is that we only need to find out the machine which needs the maximum moves.
         * This maximum moves is the min moves to make all the machine having same dresses.
         */
    	int moves = 0, giveToNext = 0, tmp = 0;
    	for (final int machine : machines) {
    		tmp = machine + giveToNext -avg;
    		moves = Math.max(moves, getMoves(giveToNext, tmp));
    		giveToNext = tmp;
    	}
    	
    	return moves;	
    }
    
    private static int getMoves(final int gotFromPrev, final int giveToNext) {
    	if (gotFromPrev >= 0) { 
    		/* 
    		 * In this case, this machine has got some dresses from prev machine.
    		 * Then 
    		 * (1) if giveToNext >= 0, it means this machine also needs to move some dresses to next machine,
    		 * so the giveToNext = the necessary moves happening on this machine.
    		 * (2) if giveToNext < 0, it means the next machine needs to move some dresses to this machine,
    		 * so the necessary moves happening on this machine itself = 0.
    		 */
    		return giveToNext >= 0 ? giveToNext : 0;
    	} else {
    		/* 
    		 * In this case, this machine has to move some dresses to prev machine.
    		 * So at least, the necessary moves on this machine is already (-gotFromPrev).
    		 * Then 
    		 * (1) if giveToNext >= 0, it means this machine also needs to move some dresses to next machine,
    		 * so the necessary moves happening on this machine = giveToNext + (-gotFromPrev)
    		 * (2) if giveToNext < 0, it means the next machine needs to move some dresses to this machine,
    		 * so the necessary moves happening on this machine itself is just (-gotFromPrev).
    		 */
    		return giveToNext >= 0 ? giveToNext-gotFromPrev : -gotFromPrev;
    	}
    }
    

    '''


Log in to reply
 

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