Make Array Zero by Subtracting Equal Amounts
Easy
You are given a non-negative integer array nums. In one operation, you must:
- Choose a positive integer
xsuch thatxis less than or equal to the smallest non-zero element innums. - Subtract
xfrom every positive element innums.
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 <= 1000 <= nums[i] <= 100
What is the most efficient way to determine the minimum number of operations to make every element in nums equal to 0?
Solution
Brute Force Approach
A naive approach would be to simulate the operations as described in the problem statement. In each operation, find the smallest non-zero element and subtract it from all other positive elements. Count the number of operations until all elements become zero.
def min_operations_brute_force(nums):
operations = 0
while any(nums):
smallest_positive = float('inf')
for num in nums:
if num > 0 and num < smallest_positive:
smallest_positive = num
if smallest_positive == float('inf'):
break
for i in range(len(nums)):
if nums[i] > 0:
nums[i] -= smallest_positive
operations += 1
return operations
Time Complexity
O(M*N), where N is the length of the array nums, and M is the number of operations required to make all elements zero. In the worst case, M can be as large as the maximum value in nums.
Space Complexity
O(1), as we are modifying the input array in place.
Optimal Approach
The key insight is that the number of operations is equal to the number of distinct positive integers in the array. We can use a set to keep track of the distinct positive numbers. The size of the set will give the minimum number of operations.
def min_operations_optimal(nums):
distinct_positive = set()
for num in nums:
if num > 0:
distinct_positive.add(num)
return len(distinct_positive)
Time Complexity
O(N), where N is the length of the array nums. This is because we iterate through the array once.
Space Complexity
O(K), where K is the number of distinct positive integers in nums. In the worst case, K can be equal to N if all positive integers are distinct.
Edge Cases
- Empty Array: Although the constraints state that
1 <= nums.length <= 100, we should consider the case where the input array is empty. In this case, the function should return 0. - Array with all zeros: If the input array contains only zeros, the function should return 0.
- Array with a single element: If the array contains a single element, the function should return 1 if the element is positive, and 0 if the element is 0.
- Array with duplicate positive numbers: The optimal solution handles this case correctly because a set is used to store distinct positive numbers.
