Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3

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

Solution

Method 1 - Using Set

Observation

  1. Identical elements remain identical, so → Deduplicate them.
  2. Distinct elements remain distinct until zero, so → Count the unique elements.

Explanation

Return the count of distinct positive elements.

Code

1
2
3
4
5
6
7
8
9

public int minimumOperations(int[] nums) {
	Set<Integer> set = new HashSet<>();
	for (int num: nums) {
		if (num > 0) {
			set.add(num);
		}
	}
	return set.size();
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)