3012. Minimize Length of Array Using Operations

Problem Description

The provided problem asks us to perform a series of operations on an array nums containing positive integers to minimize its length. The operations can be executed any number of times and consist of the following steps:

Choose two different indices i and j where both nums[i] and nums[j] are greater than zero.
Calculate nums[i] % nums[j] (the remainder of the division of nums[i] by nums[j]) and append the result to the end of the array.
Remove the elements at indices i and j from the array.

We aim to find the minimum possible length of the array after performing these operations repeatedly.

Intuition

To develop the intuition for the solution, we consider the behavior of the modulo operation and how it can influence the array's length:

If there is the smallest number in the array, mi, that does not evenly divide at least one other element, using mi and this other element in an operation would create a new, smaller number than mi.
The presence of a smaller number means we can keep performing the operation, pairing the new smaller number with others to continue reducing the size of the array until only one number remains.

Keeping these points in mind, we consider two scenarios:

If there is an element x in nums such that x % mi is not zero, the array can be reduced to a single element, hence the minimum possible length is 1.
If all elements in nums are multiples of mi, we can use mi to eliminate them by pairing each occurrence with another mi. Doing so repeatedly halves the group of mi elements (plus one if the count is odd), leading to the final minimum length being the count of mi divided by 2, rounded up.

This reasoning leads to the solution approach implemented in the given code.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation of the solution is concise, leveraging the minimum element in the array and the count of occurrences of this minimum element:

Finding the Minimum Element: The first step is to find the minimum element mi in the list using the Python built-in function min(). This element is crucial because it is the smallest possible remainder we can generate (since any number modulo itself is 0).
Checking for Non-multiples of the Minimum Element: We then check whether every element in the array is a multiple of mi. This is done by iterating through each element x in nums and checking if x % mi yields a non-zero value. This can be achieved using the built-in any() function in Python which returns True if at least one element satisfies the condition. If we find that x % mi is not zero for some element x, it implies that we can reduce the size of the array to 1 by performing operations using x and mi. Hence, in this case, the algorithm returns 1.
Counting Instances of the Minimum Element: If all elements in the array are multiples of mi, it means no operations can produce a smaller element than mi. Therefore, the next step is to count how many times mi occurs in the array using the count() method. If the minimum element mi occurs, for example, two times, operations can be performed to reduce these to one instance of mi and so forth for pairs of mi.
Calculating the Final Array Length: Lastly, we determine the minimum length of the array by dividing the count of mi by 2 and rounding up. The rounding up is accomplished by adding 1 to the count and then performing an integer division by 2 ((nums.count(mi) + 1) // 2).

Here's the breakdown of the algorithm used in the Solution class:

Get the smallest element mi in nums as mi = min(nums).
Check if there's any element in nums that is not a multiple of mi with any(x % mi for x in nums):
- If true, return 1.
- If false, calculate (nums.count(mi) + 1) // 2 and return the result.

This process uses constant space (no extra data structures are needed other than variables to store the minimum element and the count) and requires time complexity of O(n) due to the single pass through the list nums to count elements and check for non-multiples of mi.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose our input array nums is [6, 4, 4, 2].

Finding the Minimum Element: First, we find the smallest item in nums. In our example, mi = min(nums) would yield mi = 2.
Checking for Non-multiples of the Minimum Element: Next, we check if each element in nums is a multiple of mi. We iterate over the array and use the modulo operation. In this case, 6 % 2 is 0, 4 % 2 is 0, and 4 % 2 is again 0. Since all results are 0, every element is a multiple of mi.
Counting Instances of the Minimum Element: Since all elements are multiples of mi, we now count how many times mi appears in nums. With nums.count(2), we get the value 1, indicating that the element 2 appears once in the array.
Calculating the Final Array Length: Finally, to find the minimum possible length of the array, we divide the count by 2 and round up. With only one 2 in the array, we apply (nums.count(mi) + 1) // 2, which equals (1 + 1) // 2, yielding a final result of 1.

Therefore, for the input array [6, 4, 4, 2], the minimum possible length of the array after performing the operations is 1.

This example takes us through the intuitive approach to reduce the array's length by focusing on the minimum element and checking if we can produce a smaller number through the modulo operation. As we found that all elements were multiples of the smallest element, we determined that no further reduction is possible other than pairing the like terms, resulting in the smallest possible length of 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumArrayLength(self, nums: List[int]) -> int:
5        # Find the minimum value in the nums list
6        minimum_value = min(nums)
7      
8        # Check if any number in the list is not divisible by the minimum value
9        if any(number % minimum_value for number in nums):
10            # If there's at least one number not divisible by minimum_value, 
11            # the minimum array length required is 1
12            return 1
13      
14        # Count the occurrences of the minimum value in nums
15        count_min_value = nums.count(minimum_value)
16      
17        # Calculate the minimum array length by dividing the count of minimum_value by 2
18        # and rounding up to the nearest integer if necessary
19        return (count_min_value + 1) // 2
20

1import java.util.Arrays;
2
3class Solution {
4    public int minimumArrayLength(int[] nums) {
5        // Find the minimum value in the array using a stream
6        int minElement = Arrays.stream(nums).min().getAsInt();
7      
8        // Initialize a count to track the occurrence of the minimum element
9        int minCount = 0;
10      
11        // Iterate over each element in the array
12        for (int element : nums) {
13            // If the element is not divisible by the minimum element,
14            // the minimum length needed is 1, so return 1
15            if (element % minElement != 0) {
16                return 1;
17            }
18            // If the element is equal to the minimum element,
19            // increment the count of the minimum element
20            if (element == minElement) {
21                ++minCount;
22            }
23        }
24      
25        // Return half of the count of the minimum element plus one, rounded down.
26        // This determines the minimum array length required.
27        return (minCount + 1) / 2;
28    }
29}
30

1#include <vector> // Required for std::vector
2#include <algorithm> // Required for std::min_element function
3
4class Solution {
5public:
6    // Function to find the minimum array length required
7    int minimumArrayLength(vector<int>& nums) {
8        // Find the smallest element in the array
9        int minValue = *std::min_element(nums.begin(), nums.end());
10        // Initialize count of elements equal to the smallest element
11        int countMinValue = 0; 
12      
13        // Iterate over all elements in the array
14        for (int num : nums) {
15            // If current element is not a multiple of the smallest element,
16            // return 1, as we cannot equalize array with elements having 
17            // a common factor with the smallest element
18            if (num % minValue) {
19                return 1;
20            }
21            // Increase count if current element is equal to the smallest element
22            countMinValue += (num == minValue);
23        }
24      
25        // Calculate and return the minimum array length required by dividing the count
26        // of smallest elements by 2 and adding 1, then taking the ceiling of the result
27        // Since countMinValue is integer, add 1 before division to achieve the ceiling effect
28        return (countMinValue + 1) / 2;
29    }
30};
31

1function minimumArrayLength(nums: number[]): number {
2    // Find the minimum element in the array.
3    const minimumElement = Math.min(...nums);
4    let minimumElementCount = 0;
5
6    // Iterate over each number in the array.
7    for (const number of nums) {
8        // If any number is not divisible by the minimum element,
9        // the minimum array length that satisfies the condition is 1.
10        if (number % minimumElement !== 0) {
11            return 1;
12        }
13        // Count how many times the minimum element appears in the array.
14        if (number === minimumElement) {
15            minimumElementCount++;
16        }
17    }
18
19    // Return the half of the count of the minimum element (rounded up).
20    // This is due to the right shift operation which is equivalent to Math.floor((minimumElementCount + 1) / 2).
21    return (minimumElementCount + 1) >> 1;
22}
23

Time and Space Complexity

The time complexity of the given code can be discussed as follows. The min(nums) call iterates through the nums list once to find the minimum value, which takes O(n) time where n is the length of nums. The any(...) function in the next line also performs another iteration over nums, hence taking up to O(n) time in the worst case. The call to nums.count(mi) is yet another iteration through the list, which is O(n) as well.

Adding these up, we see that the function potentially iterates through the list three times independently. However, since we don't multiply independent linear traversals but rather add them, the overall time complexity remains O(n).

The space complexity does not depend on the size of the input as no additional space is allocated based on nums. No extra storage scales with the size of the input; only a fixed number of single-value variables (mi) are used. Therefore, the space complexity of the code is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: