BinarySearch 0743 Equalize List Sums with Minimal Updates

Problem statement

https://binarysearch.com/problems/Equalize-List-Sums-with-Minimal-Updates/

Solution

Equal to Leetcode 1775. Equal Sum Arrays With Minimum Number of Operations.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, A, B):
        if sum(A) > sum(B):
            A, B = B, A
        moves = sorted([6 - x for x in A] + [x - 1 for x in B])[::-1]
        gap = sum(B) - sum(A)
        it = 0
        
        while gap > 0 and it < len(moves):
            gap -= moves[it]
            it += 1
            
        return it if gap <= 0 else -1