Make Array Zero by Subtracting Equal Amounts

Easy
1795.

Make Array Zero by Subtracting Equal Amounts

Make Array Zero by Subtracting Equal Amounts is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.

You are given an array nums of non-negative integers. In one operation you:

  • choose a positive integer x no larger than the smallest non-zero element of nums, and
  • subtract x from every positive element.

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

Example 1

Input
nums = [4,0,4,2,2]
Output
2
Explanation
Subtract 2: `[2,0,2,0,0]`. Subtract 2 again: all zeros.

Example 2

Input
nums = [0,0]
Output
0
Explanation
The array is already all zeros.

Example 3

Input
nums = [7,1,3,7,1]
Output
3
Explanation
Subtract 1, then 2, then 4: the distinct values 1, 3 and 7 each need their own step.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Make Array Zero by Subtracting Equal Amounts — Solution

Make Array Zero by Subtracting Equal Amounts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Make Array Zero by Subtracting Equal Amounts is an easy coding problem on arrays, hash table and sorting, asked in Amazon interviews.

Problem statement

You are given an array nums of non-negative integers. In one operation you:

  • choose a positive integer x no larger than the smallest non-zero element of nums, and
  • subtract x from every positive element.

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

Example 1

Input: nums = [4,0,4,2,2]
Output: 2
Explanation: Subtract 2: `[2,0,2,0,0]`. Subtract 2 again: all zeros.

Example 2

Input: nums = [0,0]
Output: 0
Explanation: The array is already all zeros.

Example 3

Input: nums = [7,1,3,7,1]
Output: 3
Explanation: Subtract 1, then 2, then 4: the distinct values 1, 3 and 7 each need their own step.

Constraints

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

Hints for Make Array Zero by Subtracting Equal Amounts

  1. Hint 1

    Subtracting the smallest positive element each time is never worse than subtracting less.

  2. Hint 2

    Each such operation turns every copy of the current minimum into 0 and keeps distinct values distinct.

  3. Hint 3

    So the answer is the number of distinct positive values.

How to solve Make Array Zero by Subtracting Equal Amounts

Equal elements stay equal through every operation, and each operation can zero out at most one group of equal values (the smallest). Taking x = the current minimum does exactly that, so the answer is the count of distinct non-zero values.

Approach

  1. Insert every positive element into a set.
  2. Return the size of the set.

Why it works

An operation subtracts the same amount from every positive element, so two positive elements that differ keep differing until the smaller reaches 0 — they can never reach 0 in the same operation. Hence at least one operation per distinct positive value is needed. Choosing x equal to the smallest positive value zeroes exactly that value's group each time, meeting the bound.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Zero is not counted — elements already at 0 are untouched.
  • Duplicates collapse into one operation; counting elements instead of distinct values overcounts.

Reference solution

Python

from typing import List

def minimumOperations(nums: List[int]) -> int:
    return len({x for x in nums if x > 0})

Java

public static int minimumOperations(int[] nums) {
    boolean[] seen = new boolean[101];
    int count = 0;
    for (int x : nums) {
        if (x > 0 && !seen[x]) { seen[x] = true; count++; }
    }
    return count;
}

C++

int minimumOperations(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) if (x > 0) seen.insert(x);
    return (int)seen.size();
}

JavaScript

var minimumOperations = function(nums) {
    var seen = new Set();
    for (var i = 0; i < nums.length; i++) if (nums[i] > 0) seen.add(nums[i]);
    return seen.size;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets