+ 5

Challenge: Super Washing Machine

You have¬†n¬†super washing machines on a line. Initially, each washing machine has some dresses or is empty. For each¬†move, you could choose¬†any m¬†(1 ‚ȧ m ‚ȧ n) washing machines, and pass¬†one dress¬†of each washing machine to one of its adjacent washing machines¬†at the same time¬†. Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the¬†minimum number of moves¬†to make all the washing machines have the same number of dresses.

1st Oct 2017, 6:17 AM
Kartikey Sahu
Kartikey Sahu - avatar
8 Answers
+ 3
If it is not possible to do it, return -1. Example1 Input: [1,0,5] Output: 3 Explanation: 1st move: 1 0 <-- 5 => 1 1 4 2nd move: 1 <-- 1 <-- 4 => 2 1 3 3rd move: 2 1 <-- 3 => 2 2 2 Example2 Input: [0,3,0] Output: 2 Explanation: 1st move: 0 <-- 3 0 => 1 2 0 2nd move: 1 2 --> 0 => 1 1 1 Example3 Input: [0,2,0] Output: -1 Explanation: It's impossible to make all the three washing machines have the same number of dresses. Note: The range of n is [1, 10000].The range of dresses number in a super washing machine is [0, 1e5].
1st Oct 2017, 6:17 AM
Kartikey Sahu
Kartikey Sahu - avatar
+ 8
For the sake of the algorithm - can we move a dress from a machine to *any* other machine, skipping the adjacency, provided that we increase the move counter by the difference between the two machines' positions?
1st Oct 2017, 7:03 AM
Kuba SiekierzyŇĄski
Kuba SiekierzyŇĄski - avatar
+ 6
That's what I meant, actually. So if I increase the counter by 3 not 1, it's okay?
1st Oct 2017, 7:12 AM
Kuba SiekierzyŇĄski
Kuba SiekierzyŇĄski - avatar
+ 3
Yeah, okay
1st Oct 2017, 7:21 AM
Kartikey Sahu
Kartikey Sahu - avatar
+ 2
No you can't move to any washing machine. If you moved to 3rd washing machine, the total move will be 3 instead 1 as you can't go directly there
1st Oct 2017, 7:06 AM
Kartikey Sahu
Kartikey Sahu - avatar
+ 1
My response in Ruby: https://code.sololearn.com/cO80d3k72b0P/?ref=app Quick and still needs a bit of polish, but runnable. Allows only movements of single dresses between adjacent machines. Takes user input number to represent dresses in machines (each digit representing those dresses in a single washing machine).
1st Oct 2017, 8:26 AM
André
André - avatar
1st Oct 2017, 6:34 PM
ysraelcon
ysraelcon - avatar
+ 1
I reworked and fixed up my code, now it better handles the trickier cases I've thrown at it. Should show the optimal minimum dress switches! https://code.sololearn.com/cO80d3k72b0P/?ref=app (Again, takes user input to represent dresses in machines, with each digit representing the number of dresses in a single machine.)
3rd Oct 2017, 2:29 PM
André
André - avatar