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
andj
where bothnums[i]
andnums[j]
are greater than zero. - Calculate
nums[i] % nums[j]
(the remainder of the division ofnums[i]
bynums[j]
) and append the result to the end of the array. - Remove the elements at indices
i
andj
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, usingmi
and this other element in an operation would create a new, smaller number thanmi
. - 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
innums
such thatx % 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 ofmi
, we can usemi
to eliminate them by pairing each occurrence with anothermi
. Doing so repeatedly halves the group ofmi
elements (plus one if the count is odd), leading to the final minimum length being the count ofmi
divided by 2, rounded up.
This reasoning leads to the solution approach implemented in the given code.
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 functionmin()
. 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 elementx
innums
and checking ifx % mi
yields a non-zero value. This can be achieved using the built-inany()
function in Python which returnsTrue
if at least one element satisfies the condition. If we find thatx % mi
is not zero for some elementx
, it implies that we can reduce the size of the array to 1 by performing operations usingx
andmi
. 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 thanmi
. Therefore, the next step is to count how many timesmi
occurs in the array using thecount()
method. If the minimum elementmi
occurs, for example, two times, operations can be performed to reduce these to one instance ofmi
and so forth for pairs ofmi
. -
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
innums
asmi = min(nums)
. - Check if there's any element in
nums
that is not a multiple ofmi
withany(x % mi for x in nums)
:- If true, return
1
. - If false, calculate
(nums.count(mi) + 1) // 2
and return the result.
- If true, return
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 EvaluatorExample 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 yieldmi = 2
. -
Checking for Non-multiples of the Minimum Element: Next, we check if each element in
nums
is a multiple ofmi
. We iterate over the array and use the modulo operation. In this case,6 % 2
is0
,4 % 2
is0
, and4 % 2
is again0
. Since all results are0
, every element is a multiple ofmi
. -
Counting Instances of the Minimum Element: Since all elements are multiples of
mi
, we now count how many timesmi
appears innums
. Withnums.count(2)
, we get the value1
, indicating that the element2
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 of1
.
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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.