This 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. check parity), and whether the smallest number can reach the maximum by the time all other numbers have reached the maximum.
def is_possible(nums: List[int]) -> bool:
smallest, largest = min(nums), max(nums)
total_needed = sum(largest - x for x in nums)
if total_needed % 2 == 1:
return False
return 2 * (largest - smallest) <= total_needed
this gives:
assert is_possible([6, 6, 10]) == True
assert is_possible([2, 1, 2, 3]) == True
assert is_possible([1, 5, 5, 9]) == True
assert is_possible([1, 2, 9]) == False
assert is_possible([1, 4, 9, 10]) == False
assert is_possible([1, 6, 6, 9]) == False
A more specific problem statement
One unfortunate feature of this problem is that despite the intuitively simple solution, a full proof of this solution is rather long.
The original statement of the problem has caused confusion over the meaning of the phrase 'max array', so I'll try to give a precise mathematical description of the problem, and then transform that. This will then explain why the code is implementing the natural 'greedy strategy' for the problem, and why that works.
Original Problem: Given a zero-indexed array of positive integers A of length n > 1, you are allowed to perform the following operation any number of times: Choose two distinct indices i, j with 0 <= i < j < n, such that A[i] < max(A) and A[j] < max(A), and increment A[i] and A[j]. Determine whether you can make all of the array elements equal.
The greedy strategy
The 'greedy' or brute-force solution to this problem, if performance wasn't a concern, would be to select the two smallest elements from A and increment them, repeating this until either all or all but one element from A was equal to max(A). If exactly one element isn't equal to max(A), we failed and the task is impossible (this statement requires a proof); otherwise it is clearly possible.
def is_possible_brute_force(nums: List[int]) -> bool:
largest = max(nums)
nums.sort()
while nums[0] != largest:
first = nums.pop(0)
second = nums.pop(0)
if second == largest and first != largest: # If exactly one number not max
return False
bisect.insort(nums, first+1)
bisect.insort(nums, second+1)
return all(x == largest for x in nums) # Always true
Our goal is to simulate the result of this procedure, without actually doing it. We can observe immediately that the task is impossible if the sum of gaps between elements of A and max(A), which we might call total_needed, is odd. It's also true that we can apply the following transformation to the problem without changing the answer:
New Problem: Let M = max(A). Let B be A after the transform A[i] -> M - A[i]. Our allowed operation is now to decrement two distinct indices of B, and our goal is to reach the zero array.
It's easier to think in terms of B and decrements. The first strategy you might think of is: repeatedly decrement the two largest elements of B, i.e. the greedy strategy. This strategy turns out to be optimal, finding a solution whenever it exists.
Let Max_B = max(B) and let Sum_B = sum(B). Since we know that no solution exists if Sum_B is odd, we can assume that Sum_B is even from here on. There are two possibilities:
Max_B > Sum_B - Max_B. In this case, no matter what we do, after performing Sum_B - Max_B decrements, all elements except Max_B are zero, so no solution is possible.Max_B <= Sum_B - Max_B. In this case, a solution is always possible.
To prove (2), it suffices to prove two things:
i. If Max_B <= Sum_B - Max_B, then after decrementing the two largest elements, we still have Max_B <= Sum_B - Max_B for our new array.
ii. The only configuration where no moves are possible yet B is nonzero is when exactly one element of B is nonzero; in this case, Max_B > Sum_B - Max_B
The proof of the first statement is algebraic manipulation and case analysis that is fairly unsurprising, so I'll omit that from this already lengthy proof. The first Python code snippet can now be understood as checking the parity of total_needed, and whether we are in situation (1) or (2) above.
Edit: The original posted version of the code had a mistake in the final line, using an incorrect variable name and a flipped inequality sign, compared to the equation in the explanation and proof. Credit and thanks goes to user Breaking Not So Bad for catching this.
