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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Array Zero by Subtracting Equal Amounts

Number: 2436

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given a non-negative integer array nums, you must repeatedly choose a positive integer x (which is less than or equal to the smallest non-zero element in nums) and subtract it from every positive element in the array. The goal is to make every element equal to 0 in the minimum number of operations.

Key Insights

  • The minimum number of operations required equals the number of distinct positive numbers in the array.
  • Each operation subtracts the smallest positive number, effectively "removing" one unique layer of values.
  • Instead of simulating each subtraction, counting the unique positive numbers gives a direct answer.

Space and Time Complexity

Time Complexity: O(n) – We only need to iterate through the array once. Space Complexity: O(n) – In the worst case, the set may hold all distinct elements.

Solution

The solution leverages a set data structure to track distinct positive numbers in the array. Since each unique positive number represents one subtraction operation (removing that "layer" of numbers), the number of operations required equals the size of this set. This approach simplifies the problem by avoiding repetitive subtraction operations and simulates the process in a single pass.

Code Solutions

# Function to compute the minimum number of operations required to make all elements zero
def make_array_zero(nums):
    # Use a set to collect all unique positive numbers
    unique_positives = set()
    # Iterate through each number in the list
    for num in nums:
        # If the number is positive, add it to the set
        if num > 0:
            unique_positives.add(num)
    # The minimum operations required is the number of unique positive numbers
    return len(unique_positives)

# Example usage:
nums = [1, 5, 0, 3, 5]
print(make_array_zero(nums))  # Expected output: 3
← Back to All Questions