Minimize Length of Array Using Operations
You are given a 0-indexed integer array nums containing positive integers.
Your task is to minimize the length of nums by performing the following operations any number of times, including zero:
- Select two distinct indices
iandjfromnums, such thatnums[i] > 0andnums[j] > 0. - Insert the result of
nums[i] % nums[j]at the end ofnums. - Delete the elements at indices
iandjfromnums.
Return an integer denoting the minimum length of nums after performing the operation any number of times.
Example 1
Input
nums = [1,4,3,1]Output
1The array can be reduced through the described operations to
[0], and it can be shown that length 1 is the minimum achievable length.Example 2
Input
nums = [5,5,5,10,5]Output
2The array can be reduced through the described operations to
[0,0], and it can be shown that length 2 is the minimum achievable length.Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9