We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Make Array Zero by Subtracting Equal Amounts

Difficulty: Easy

Problem Description

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.

Key Insights

  • The number of operations required is equal to the number of distinct positive integers in the array.
  • In each operation, you can eliminate at least one positive integer by selecting the smallest one.
  • Zeros do not contribute to the operations since they do not need to be changed.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can utilize a set to keep track of distinct positive integers in the array. The size of this set will represent the minimum number of operations needed since each unique positive integer will require one operation to eliminate it. The algorithm proceeds as follows:

  1. Initialize an empty set to store distinct positive integers.
  2. Iterate through the array and add each positive integer to the set.
  3. The answer will be the size of the set, which counts how many unique positive integers exist in the array.

Code Solutions

def minimumOperations(nums):
    # Using a set to track distinct positive integers
    distinct_positive = set()
    
    # Iterate through the array
    for num in nums:
        if num > 0:
            distinct_positive.add(num)  # Add positive numbers to the set
    
    # The size of the set is the answer
    return len(distinct_positive)
← Back to All Questions