Skip to content

2357. Make Array Zero by Subtracting Equal Amounts

SourceWeekly Contest 304 Q1DifficultyEasyRating1225

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.

 

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 <= 100
  • 0 <= nums[i] <= 100

Solutions

Solution 1: Hash Table or Array

Thinking

Each move picks a positive \(x\) and subtracts it from every entry \(\ge x\), which removes one distinct positive value. \(n \le 100\), so counting those values is enough.

Zeros never change and never create new positives. The answer is the size of \(\{x \in nums: x>0\}\).

We observe that in each operation, all identical nonzero elements in the array \(\textit{nums}\) can be reduced to \(0\). Therefore, we only need to count the number of distinct nonzero elements in \(\textit{nums}\), which is the minimum number of operations required. To count the distinct nonzero elements, we can use a hash table or an array.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

1
2
3
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        return len({x for x in nums if x})

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int minimumOperations(int[] nums) {
        boolean[] s = new boolean[101];
        s[0] = true;
        int ans = 0;
        for (int x : nums) {
            if (!s[x]) {
                ++ans;
                s[x] = true;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        bool s[101]{};
        s[0] = true;
        int ans = 0;
        for (int& x : nums) {
            if (!s[x]) {
                ++ans;
                s[x] = true;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func minimumOperations(nums []int) (ans int) {
    s := [101]bool{true}
    for _, x := range nums {
        if !s[x] {
            s[x] = true
            ans++
        }
    }
    return
}

1
2
3
4
5
function minimumOperations(nums: number[]): number {
    const s = new Set(nums);
    s.delete(0);
    return s.size;
}

1
2
3
4
5
6
7
8
use std::collections::HashSet;
impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut s = nums.iter().collect::<HashSet<&i32>>();
        s.remove(&0);
        s.len() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int minimumOperations(int* nums, int numsSize) {
    int vis[101] = {0};
    vis[0] = 1;
    int ans = 0;
    for (int i = 0; i < numsSize; i++) {
        if (vis[nums[i]]) {
            continue;
        }
        vis[nums[i]] = 1;
        ans++;
    }
    return ans;
}

Comments