Make Array Zero by Subtracting Equal Amounts

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: nums
    integer :: i, x, min_operations

    ! Example 1
    nums = [1, 5, 0, 3, 5]
    write(*,*) 'Example 1:'
    write(*,*) 'Input:', nums
    call solve(nums, min_operations)
    write(*,*) 'Output:', min_operations
    write(*,*) ''

    ! Example 2
    nums = [0]
    write(*,*) 'Example 2:'
    write(*,*) 'Input:', nums
    call solve(nums, min_operations)
    write(*,*) 'Output:', min_operations
    write(*,*) ''

contains

    subroutine solve(nums, min_operations)
        implicit none
        integer, intent(in) :: nums(:)
        integer, intent(out) :: min_operations
        integer :: i, x

        min_operations = 0
        do while (any(nums > 0))
            x = minval(nums(nums > 0), mask=nums > 0)
            min_operations = min_operations + 1
            do i = 1, size(nums)
                if (nums(i) > 0) then
                    nums(i) = nums(i) - x
                end if
            end do
        end do
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MinimumOperations
    implicit none
    private
    public :: minimumOperations
contains
    integer function minimumOperations(nums) result(minOps)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: x, i, minOps

        ! Find the smallest non-zero element in nums
        x = minval(nums, mask = nums /= 0)

        ! Initialize the minimum number of operations to 0
        minOps = 0

        ! Loop through the array and subtract x from each positive element
        do i = 1, size(nums)
            if (nums(i) > 0) then
                nums(i) = nums(i) - x
                minOps = minOps + 1
            end if
        end do
    end function minimumOperations
end module MinimumOperations

program test_minimumOperations
    use MinimumOperations
    implicit none
    integer, parameter :: nums1(5) = [1, 5, 0, 3, 5]
    integer, parameter :: nums2(1) = [0]
    integer :: minOps1, minOps2

    minOps1 = minimumOperations(nums1)
    write (*,*) "Minimum operations for nums1:", minOps1
    minOps2 = minimumOperations(nums2)
    write (*,*) "Minimum operations for nums2:", minOps2
end program test_minimumOperations
🌐 Data from online sources 
def minOperations(nums):
    count = 0
    nums.sort()
    i = 0

    while i < len(nums):
        if nums[i] > 0:
            target = nums[i]
            while i < len(nums) and nums[i] == target:
                i += 1
            count += 1
        else:
            i += 1

    return count
  1. Sort the given array in non-descending order.
  2. Initialize a variable count to store the number of operations.
  3. Iterate through the sorted array.
  4. If the current element is positive, find the count of elements with the same value.
  5. Add this count to the overall count and update i to skip these elements.
  6. If the current element is not positive, just move to the next element.
  7. Return the overall count (number of operations).

This algorithm works because after sorting the array, we traverse it and count distinct positive numbers. Each distinct positive number corresponds to a unique operation that reduces it to zero while also reducing any larger numbers in the array. Since the operation only affects positive numbers, we can skip the zero elements. By the end of the algorithm, we have counted the minimum number of operations required to make all elements equal to zero.

🌐 Data from online sources 
int minOperations(vector<int>& nums) {
    int count = 0;
    std::sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0) {
            count += nums.end() - (std::upper_bound(nums.begin() + i, nums.end(), nums[i]));
            i = (std::upper_bound(nums.begin(), nums.end(), nums[i])) - nums.begin() - 1;
        }
    }

    return count;
}
  1. Sort the given array in non-descending order.
  2. Initialize a variable count to store the number of operations.
  3. Iterate through the sorted array.
  4. If the current element is positive, find the count of elements with the same value.
  5. Add this count to the overall count and update i to skip these elements.
  6. If the current element is not positive, just move to the next element.
  7. Return the overall count (number of operations).

This algorithm works because after sorting the array, we traverse it and count distinct positive numbers. Each distinct positive number corresponds to a unique operation that reduces it to zero while also reducing any larger numbers in the array. Since the operation only affects positive numbers, we can skip the zero elements. By the end of the algorithm, we have counted the minimum number of operations required to make all elements equal to zero.