last day (15 days later) » 

1:30 AM
6
A: Increment two array elements at a time so all equal the max value

kcsquaredThis is actually a known interview/programming contest question, but it's usually presented as "Given an array of positive integers, can you reduce them all to zero, two (or k) at a time?" There is a simple solution: we only need to check whether we can reach the desired sum in steps of two (i.e....

 
Can you please explain this line : total_needed = sum(largest - x for x in nums)
 
@mustafa1993 Sure, I added an explanation. It's the count of single increment operations to get a 'max array', which must be even for the transformation to be possible.
[4, 2, 2, 6] -> [5, 3, 2, 6] -> [6, 3, 3, 6] -> [6, 4, 4, 6] -> ... -> [6, 6, 6, 6] is the transformation. It's of course possible there's an off by one error in the code, but that example doesn't show it @גלעדברקן
@גלעדברקן Sure, give me a little while to add a fuller proof. Full disclosure, I actually solved a basically equal problem in a Leetcoding programming contest recently. I can try to rephrase the argument for why it works, but there's dozens of explanations for this problem already so my contribution won't be all that unique.
@גלעדברקן I'm not sure why your comments got deleted, but I've added an almost complete proof.
 
What about [6,6,10] or [1,4,9,10]?
 
Sorry, I deleted them. Looking at the proof now. Thanks for posting it!
@Breakingnotsobad could kcsquared have meant return 2 * (largest - smallest) <= total_needed for the last line?
How is [1, 6, 6, 9] True?
 
@Breakingnotsobad You're absolutely right, thank you so much for doing those tests. This is rather embarrassing; I was so focused on proving the correctness of the strategy that I missed a large mistake on the last line of the code. Even one of the examples and output I showed, (1, 6, 6, 9), shows that the code is wrong. I've reread the proof and explanation and everything there is correct; properly implementing the condition 'Max_B <= Sum_B - Max_B' would mean the last line should be 2 * (largest - smallest) <= total_needed.
@גלעדברקן You're completely correct, and that should be the final line to match the explanation; I didn't test the code properly since I knew the strategy worked and had solved this recently. I'm fairly new to Stackoverflow so I'm not entirely sure what to do; I'm planning to edit the code to be correct (the proof is fine, and I'm currently writing tests for the new code), mention the change, and credit Breakingnotsobad, but I don't know if it's more appropriate to delete and re-post the answer or make it a community wiki.
 
1:30 AM
No idea. Whatever you like, as far as I'm concerned.
 
@Breakingnotsobad Running those two examples, I'm getting False and True respectively on the updated code and several verifying functions, and can replicate those results by hand: [4, 6, 8] cannot become [8,8,8], and [1,4,7,10] can become [10,10,10,10]. Are you saying the last line should be == instead of <=, or that the strategy has another flaw?
@Breakingnotsobad Besides the previous error in the last line of the code (which was substantial, since both a variable name and an inequality sign were flipped), I'm not aware of any errors in the post's logic or explanation, as this problem and solution are basically equivalent to the linked contest question. If there's any errors in the current post (possibly relating to your comment about 'have a < or >') or any logic errors besides that line, please let me know; however I have since written fairly substantial tests before I made the edit earlier today to make sure there were no typos.
@Breakingnotsobad Those examples should all be True, no? E.g. you could do [5,5,5,7] -> [5,6,6,7] -> [6,7,6,7] -> [7,7,7,7], and similarly for the other two. The single edit made to the code for this post, ever, was the one 5 hours ago of return 2 * (total_needed - smallest) >= total_needed to return 2 * (largest - smallest) <= total_needed which did fix your first example and my included example of [1, 6, 6, 9] (and also made the code match the explanation's equation). I'm happy to discuss this with you further, and I sincerely don't want to appear to be dishonestly editing the post.
 
Looks like I didn't update correctly the code :) +1
 

last day (15 days later) »