Count Operations To Obtain Zero - Leetcode Solution

Problem Statement: You have an integer array nums. You can perform the following operation any number of times on nums:

Pick any two elements x and y from nums. Pick any z in the range [0, abs(x - y)] and replace both x and y with x - z and y - z respectively. Return the minimum number of operations needed to make nums[i] == 0 for all 0 <= i < nums.length.

Solution: We can observe that the operations are commutative i.e., x - z is same as y - z. So, we can consider x - y always positive and use absolute value to calculate z. For some element in nums to become zero, there must exist another element with same value but with opposite sign. So, our goal should be to make elements in nums equal by modifying only one of them and that too to the number which is equal to its absolute value. If there are no such elements, then we can modify any element to go towards 0. We can find the count of such elements in nums by keeping a track of their absolute values using a dictionary. Let’s call this dictionary count.

Let’s walk through an example: nums = [1,1,-2] count = {1: 2, 2: 0} nums[0] and nums[1] are equal, so we modify nums[0]. We can pick any value from 0 to abs(1 - 1) i.e., 0. So, nums becomes [0, 1, -2]. And count becomes {1: 1, 2: 0, 0: 1}. We can now modify nums[1] with any value between 0 and 1 and nums becomes [0, 0, -2]. And count becomes {1:0, 2:0, 0:2}. Since, there are two zeros in nums, our task is complete and we return 2 which is the number of operations used.

Let’s see the implementation in Python:

def minOperations(nums: List[int]) -> int: count = defaultdict(int) for num in nums: abs_val = abs(num) count[abs_val] += 1

num_of_ops = 0
while len(count) > 0:
    cur_abs_val = max(count.keys())
    cur_count = count.pop(cur_abs_val)
    
    if cur_abs_val == 0:
        continue
    
    # if there are no opposite sign elements
    # modify any element to move towards 0
    if cur_abs_val not in count:
        cur_abs_val //= 2
        num_of_ops += cur_count
        count[cur_abs_val] += cur_count
        continue
    
    # modify one element
    num_of_ops += cur_count
    count[cur_abs_val * 2] += cur_count
    
    # check if elements have become 0
    if count[cur_abs_val] == 0:
        del count[cur_abs_val]
    else:
        count[cur_abs_val] -= cur_count

return num_of_ops

Time Complexity: We need to iterate through nums once to fill the count dictionary and keep iterating through it until it becomes empty. So, the time complexity of this algorithm is O(n + m*log(m)) where n is the length of nums and m is the number of distinct elements in nums. The log(m) factor comes from the fact that we need to perform a max operation on the keys of count dictionary.

Space Complexity: We need to maintain the count dictionary which can at maximum have m distinct keys. So, the space complexity of this algorithm is O(m).

1