{x}
blog image

Make Array Zero by Subtracting Equal Amounts

You are given a non-negative integer array nums. In one operation, you must:

  • Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
  • Subtract x from every positive element in nums.

Return the minimum number of operations to make every element in nums equal to 0.

 

Example 1:

Input: nums = [1,5,0,3,5]
Output: 3
Explanation:
In the first operation, choose x = 1. Now, nums = [0,4,0,2,4].
In the second operation, choose x = 2. Now, nums = [0,2,0,0,2].
In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].

Example 2:

Input: nums = [0]
Output: 0
Explanation: Each element in nums is already 0 so no operations are needed.

 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Solution Explanation

The problem asks for the minimum number of operations to reduce all elements in a non-negative integer array nums to 0. In each operation, we choose a positive integer x less than or equal to the smallest non-zero element in nums and subtract x from every positive element.

The key observation is that we only need to track the unique non-zero values in the array. Each unique non-zero value represents one operation. This is because subtracting the smallest non-zero element from all positive elements guarantees that we will either reduce some elements to zero, or create new unique non-zero values. We'll continue doing this until there are no more non-zero elements.

The most efficient way to solve this is using a set (or hash table) to store the unique non-zero elements. The size of the set after removing 0 will be the minimum number of operations.

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the length of the input array nums. This is because we iterate through the array once to populate the set. Set operations (insertion, deletion, checking for existence) typically take constant time on average.

Space Complexity: O(N) in the worst case. This is because the set could potentially store up to N unique non-zero elements. In the best case (all elements are 0 or duplicates), the space complexity would be O(1).

Code Implementation Details

The provided code in various languages demonstrates this approach:

  • Python, Java, C++, Go, TypeScript, Rust, C: All these solutions use a boolean array or a Set (or equivalent data structure) to efficiently track the unique non-zero elements. The Set automatically handles the uniqueness. The code iterates through the array, and if a non-zero element is not already in the set, it's added to the set, and the counter ans is incremented. After the loop, ans contains the number of unique non-zero values, which is the answer.

  • Python (more concise): This version utilizes set comprehension for an even more compact solution.

All the solutions effectively achieve the same goal with minor syntactic differences across languages. They all avoid unnecessary iterations or computations, making them highly efficient.