2344. Minimum Deletions to Make Array Divisible

HardArrayMathNumber TheorySortingHeap (Priority Queue)
Leetcode Link

Problem Description

This problem presents us with two arrays of positive integers, nums and numsDivide. The goal is to perform the minimum number of deletions in nums to ensure that the smallest number in nums divides all numbers in numsDivide. If no element in nums can be the divisor for every element in numsDivide, the function should return -1.

The division rule here is that an integer x divides another integer y if the remainder when y is divided by x is zero, denoted as y % x == 0.

To solve this problem, you need to consider two main steps:

  1. Identify the smallest number in nums that can be a divisor for all elements in numsDivide.
  2. Find the minimum number of deletions in nums required to make this number the smallest in nums.

Intuition

To begin, since we want a number from nums that divides all elements in numsDivide, we need to find the Greatest Common Divisor (GCD) of numsDivide. All elements of numsDivide must be divisible by this GCD, so our potential divisor in nums must also divide the GCD of numsDivide. Therefore, the smallest number in nums that also divides the GCD of numsDivide will serve as the required divisor.

With that in mind, the first step is to calculate the GCD of all elements in numsDivide using a built-in function.

Next, we search for the smallest number in nums that can divide this GCD, which can be done using a generator expression within the min function. If no such number exists in nums (when min returns the default=0), we cannot perform the desired operation, therefore we return -1.

If a divisor is found, we count the number of elements in nums that are smaller than this divisor since any such elements must be deleted for the divisor to be the smallest element in nums. The count of these elements gives us the minimum number of deletions needed. The summing using a generator expression in the return statement calculates this count and returns it.

Learn more about Math, Sorting and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the relationship between a tree and a graph?

Solution Approach

The implementation of the solution for this problem follows a straightforward approach, with the primary focus being the calculation of the Greatest Common Divisor (GCD) and the minimization of deletions.

Here's the step-by-step breakdown of the solution:

  1. Calculate the GCD of elements in numsDivide array:

    • The gcd function from the Python standard library can compute GCD of two numbers. Leveraging the unpacking operator *, we can pass all elements of numsDivide to this function to find their collective GCD.
    1x = gcd(*numsDivide)

  2. Identify the smallest number in nums that divides the GCD:

    • We use a generator expression to iterate over all the values v in nums.
    • The condition x % v == 0 ensures we only consider those elements that properly divide the GCD x.
    • The min function is used to find the smallest of such elements.
    • The default=0 is used to handle the scenario where no such divisibility is possible, which will lead to the min function returning 0.
    1y = min((v for v in nums if x % v == 0), default=0)

  3. Count and return the minimum deletions:

    • If we found a divisor y, then we count the number of elements in nums that are less than y. These elements would prevent y from being the smallest element if not deleted.
    • This count is computed with the sum of a generator expression.
    • For every element v in nums, if v < y, it adds 1 to the sum.
    1return sum(v < y for v in nums)

  4. Handle the case where no suitable divisor is found:

    • If no element in nums can divide the GCD, which means y is 0, we cannot perform the operation, so we return -1.
    1if y else -1

In summary, the solution leverages mathematical properties (divisibility and GCD), along with Python's built-in gcd function, generator expressions for memory-efficient iteration, and conditional logic to directly return the minimum number of deletions or -1 if the problem conditions cannot be met.

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

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we have the following arrays:

nums = [4, 3, 6]
numsDivide = [24, 48]

Calculating the GCD of Elements in numsDivide

First, we find the GCD of all elements in the numsDivide array:

The GCD of 24 and 48 can be found as:

GCD(24, 48) = 24

This means any divisor in nums needs to divide 24 to be a valid divisor for all numbers in numsDivide.

Identifying the Smallest Number in nums Dividing the GCD

Now, we look for the smallest number in nums that can divide the GCD 24:

  • For 4, we check if 24 % 4 == 0, which is True.
  • For 3, we check 24 % 3 and find it's also True as 24 is divisible by 3.
  • For 6, we check 24 % 6 and see that this is True as well.

All numbers [4, 3, 6] in nums can divide 24, but we need the smallest one; hence we find the min which is 3.

Counting and Returning Minimum Deletions

To make 3 the smallest number in nums, we must delete all numbers that are smaller than 3. In nums, there are no such numbers.

Therefore, the minimum number of deletions is 0.

This means no numbers from nums need to be deleted for the smallest number within it to divide all numbers in numsDivide.

Handling the Case of No Appropriate Divisor Found

Since we did find the number 3 as a suitable divisor, we did not encounter the scenario of the min function returning 0, which would have led us to return -1.

Using the aforementioned steps, the solution successfully calculates that no deletions are needed from nums so that the smallest number in nums can divide all elements in numsDivide.

Solution Implementation

1from math import gcd
2from typing import List
3
4class Solution:
5    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
6        # Calculate the greatest common divisor (GCD) of all elements in numsDivide
7        common_divisor = gcd(*numsDivide)
8      
9        # Find the smallest element in nums that is a divisor of the GCD
10        # If there is no such element, the default value will be 0
11        min_divisible = min((value for value in nums if common_divisor % value == 0), default=0)
12      
13        # If the smallest element is not found, return -1 as it's not possible
14        # to make all numsDivide elements divisible by any number in nums
15        if min_divisible == 0:
16            return -1
17      
18        # Calculate the number of operations needed by counting elements in nums
19        # that are smaller than the smallest valid divisor (min_divisible)
20        operations = sum(value < min_divisible for value in nums)
21      
22        # Return the count of operations needed
23        return operations
24
1class Solution {
2    // This method finds the minimum number of operations required 
3    // to make every number in numsDivide divisible by some number 
4    // in nums by removing the smallest numbers in nums.
5    public int minOperations(int[] nums, int[] numsDivide) {
6        // Initialize the greatest common divisor (gcd) of all numbers in numsDivide.
7        int gcdValue = 0;
8        for (int value : numsDivide) {
9            gcdValue = gcd(gcdValue, value);
10        }
11      
12        // Set an initial high value to find the minimum value in nums that divides the gcd without remainder.
13        int minDivisibleValue = Integer.MAX_VALUE;
14        for (int value : nums) {
15            if (gcdValue % value == 0) {
16                minDivisibleValue = Math.min(minDivisibleValue, value);
17            }
18        }
19      
20        // If no number was found, return -1 as it's not possible to satisfy the condition with any deletions.
21        if (minDivisibleValue == Integer.MAX_VALUE) {
22            return -1;
23        }
24      
25        // Count the numbers of operations (number of elements smaller than the minDivisibleValue to be deleted).
26        int operations = 0;
27        for (int value : nums) {
28            if (value < minDivisibleValue) {
29                operations++;
30            }
31        }
32      
33        // Return the number of operations required.
34        return operations;
35    }
36
37    // Helper method to compute the gcd of two numbers using the Euclidean algorithm.
38    private int gcd(int a, int b) {
39        // If b is zero, a is the gcd by definition.
40        return b == 0 ? a : gcd(b, a % b);
41    }
42}
43
1#include <vector>  // Required to include vector
2#include <algorithm> // Required for std::min function
3using namespace std;
4
5class Solution {
6public:
7    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
8        // Initializing gcdValue with 0 to calculate GCD of all values in numsDivide
9        int gcdValue = 0;
10        // Calculating GCD of all elements in numsDivide
11        for (int& value : numsDivide) {
12            gcdValue = gcd(gcdValue, value);
13        }
14        // Setting the minimum possible value greater than all elements in nums
15        int minValueGreaterThanAll = 1 << 30; // Large value as upper limit.
16        // Finding the smallest number in nums that divides the gcdValue without remainder
17        for (int& value : nums) {
18            if (gcdValue % value == 0) {
19                minValueGreaterThanAll = min(minValueGreaterThanAll, value);
20            }
21        }
22      
23        // If minValueGreaterThanAll is not changed, it means no such number is found. Return -1.
24        if (minValueGreaterThanAll == 1 << 30) {
25            return -1;
26        }
27        // Counting the number of operations to remove numbers smaller than minValueGreaterThanAll
28        int operationsCount = 0;
29        for (int& value : nums) {
30            operationsCount += value < minValueGreaterThanAll;
31        }
32      
33        return operationsCount; // Returning the minimum number of operations.
34    }
35  
36    // Function to calculate the gcd of two numbers
37    int gcd(int a, int b) {
38        return b == 0 ? a : gcd(b, a % b);
39    }
40};
41
1// Importing necessary functionalities from external libraries
2import { min } from 'lodash';
3
4// Function to calculate the greatest common divisor (GCD) of two numbers
5function calculateGCD(a: number, b: number): number {
6    return b === 0 ? a : calculateGCD(b, a % b);
7}
8
9// Function to find the minimum number of operations required
10function minOperations(nums: number[], numsDivide: number[]): number {
11    // Initialize gcdValue with 0 to calculate GCD of all values in numsDivide
12    let gcdValue: number = 0;
13
14    // Calculate GCD of all elements in numsDivide
15    for (const value of numsDivide) {
16        gcdValue = calculateGCD(gcdValue, value);
17    }
18
19    // Initialize minValueGreaterThanAll with a large number as an upper limit.
20    let minValueGreaterThanAll: number = 1 << 30;
21
22    // Find the smallest number in nums that divides the gcdValue without a remainder
23    for (const value of nums) {
24        if (gcdValue % value === 0) {
25            minValueGreaterThanAll = Math.min(minValueGreaterThanAll, value);
26        }
27    }
28  
29    // If minValueGreaterThanAll is not changed, no such number is found; return -1.
30    if (minValueGreaterThanAll === 1 << 30) {
31        return -1;
32    }
33
34    // Count the number of operations to remove numbers smaller than minValueGreaterThanAll
35    let operationsCount: number = 0;
36    for (const value of nums) {
37        operationsCount += value < minValueGreaterThanAll ? 1 : 0;
38    }
39
40    // Return the minimum number of operations.
41    return operationsCount;
42}
43
Not Sure What to Study? Take the 2-min Quiz๏ผš

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Time and Space Complexity

The given Python code aims to find the minimum number of operations to delete elements from nums so that the greatest common divisor (GCD) of numsDivide can divide all elements in the modified nums list. It finds the GCD of the elements of numsDivide, then finds the minimum element y in nums that is a divisor of the GCD, and counts elements in nums less than y.

Time Complexity

Let n be the length of the nums list and m be the length of the numsDivide list.

  1. gcd(*numsDivide): The function computes the GCD of all elements in numsDivide. The time complexity of the gcd function for two numbers is O(log(min(a, b))), where a and b are the two numbers. The GCD function will be called for every element in numsDivide beyond the first two. Therefore, the time complexity for this portion can be considered O(m * log (A)), where A is the average of the numsDivide list.

  2. min((v for v in nums if x % v == 0), default=0): This generator expression iterates over all elements v in nums and checks if v divides x without remainder. In the worst case, it will iterate through the entire nums list, resulting in a time complexity of O(n).

  3. sum(v < y for v in nums): This expression iterates over the list nums, and for each element, it increments the sum if the element is less than y. This operation also has a time complexity of O(n) because it goes through all n elements.

Combining these, the overall worst-case time complexity is: O(m * log (A) + 2n). Since m * log(A) and n are not related by a constant factor, we can't simplify it further. However, typically m and log(A) are much smaller than n in practical scenarios, such that we can consider it as O(n) for practical purposes.

Space Complexity

Let's analyze the space complexity of the algorithm:

  1. gcd(*numsDivide): The gcd function itself uses O(1) additional space as it only requires a constant space for the computation.

  2. min((v for v in nums if x % v == 0), default=0): The generator expression used here does not store intermediate results and computes the minimum on the fly. Therefore, it also uses O(1) space.

  3. sum(v < y for v in nums): Similar to the min function call, this sum leverages a generator expression and does not store intermediate results, so it uses O(1) additional space.

The space complexity of the entire algorithm is O(1) since all additional space used is constant and does not scale with the size of the input nums or numsDivide.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Math Basics

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

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ