Minimum Deletions to Make Array Divisible

Hard

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If this is not possible, return -1.

Note that an integer x divides y if y % x == 0.

Example 1:

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: 
The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of numsDivide.
We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums = [3,4,3].
The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide.
It can be shown that 2 is the minimum number of deletions needed.

Example 2:

Input: nums = [4,3,6], numsDivide = [8,2,6,10]
Output: -1
Explanation: 
We want the smallest element in nums to divide all the elements of numsDivide.
There is no way to delete elements from nums to allow this.

Constraints:

1 <= nums.length, numsDivide.length <= 10⁵
1 <= nums[i], numsDivide[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the arrays `nums` and `numsDivide`, and what is the range of values for the elements within each array?
Can either `nums` or `numsDivide` be empty or null?
If there is no element in `nums` that divides all elements in `numsDivide`, what should I return?
Are the elements in `nums` guaranteed to be distinct, or can there be duplicates? How should duplicates be handled when finding the smallest element?
Is it guaranteed that all elements in `numsDivide` are positive integers?

Brute Force Solution

Approach

The goal is to find the smallest number of items we need to remove from a collection so that all remaining items evenly divide a specific number. The brute force method involves trying every single possible combination of removals to see if we can achieve this goal.

Here's how the algorithm would work step-by-step:

Consider removing zero items from the collection.
Check if all the remaining items evenly divide the specified number. If so, we have a potential answer. Keep track of the smallest number of removals found so far.
Now, consider removing one item at a time. For each removed item, check if all the remaining items evenly divide the specified number.
If they do, compare the number of removals (which is one in this case) to the smallest number of removals we have found so far, and update the smallest if necessary.
Next, consider removing two items at a time, trying every possible pair. Again, check if all the remaining items divide the specified number and update the smallest number of removals if a better solution is found.
Continue this process, removing three items, then four, and so on, until we have considered removing almost all the items (removing all would leave us with nothing to divide the specified number).
The smallest number of removals found during this exhaustive process is the answer.

Code Implementation

def min_deletions_brute_force(numbers, divisible_list):
    list_length = len(numbers)
    min_deletions = list_length

    for i in range(1 << list_length):
        subset = []
        deletions = 0

        for j in range(list_length):
            if (i >> j) & 1:
                subset.append(numbers[j])
            else:
                deletions += 1

        if not subset:
            continue

        is_divisible = True
        for divisible_number in divisible_list:
            is_divisible_by_subset = False
            for subset_number in subset:
                if divisible_number % subset_number == 0:
                    is_divisible_by_subset = True
                    break
            if not is_divisible_by_subset:
                is_divisible = False
                break

        # Check if the subset satisfies the divisibility condition.
        if is_divisible:
            min_deletions = min(min_deletions, deletions)

        # Update the minimum deletions.

    if min_deletions == list_length:
        return -1

    return min_deletions

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers all possible subsets of the input array of size n. For each element, we either choose to remove it or not remove it, leading to 2^n possible combinations of removals. For each subset, we then need to check if the remaining elements divide the target number, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n) which simplifies to O(2^n) since 2^n dominates n.

Space Complexity

O(1) – The described brute force approach primarily involves iterating and comparing values. While implicitly it explores combinations, it doesn't explicitly create large auxiliary data structures proportional to the input array's size, N. Temporary variables might be used to store the current smallest number of removals, but these occupy constant space. Therefore, the auxiliary space remains constant regardless of the input size, resulting in O(1) space complexity.

Optimal Solution

Approach

To minimize deletions, we need to find the smallest number that divides all numbers in the second group and then count how many numbers in the first group are bigger than that smallest number. The key is realizing that number is the Greatest Common Divisor (GCD) of all numbers in the second group.

Here's how the algorithm would work step-by-step:

First, calculate the Greatest Common Divisor (GCD) of all the numbers in the second group. This is the largest number that divides all those numbers without any remainder.
Next, sort the first group of numbers from smallest to largest.
Go through the sorted first group, starting with the smallest number. For each number, check if the GCD calculated earlier can be divided evenly by it (no remainder).
Keep a count of how many numbers you had to check from the first group until you found one that divides the GCD. This is the minimum number of deletions needed.

Code Implementation

def minimum_deletions(numbers, divisible_list):
    def find_greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    def calculate_gcd_of_list(number_list):
        result = number_list[0]
        for i in range(1, len(number_list)):
            result = find_greatest_common_divisor(result, number_list[i])
        return result

    # Crucial step: determines divisibility target for the main list.
    divisible_gcd = calculate_gcd_of_list(divisible_list)

    numbers.sort()

    deletion_count = 0

    # Iterating to find the smallest element that divides the GCD.
    for number in numbers:
        if divisible_gcd % number == 0:
            
            # First divisor found.
            return deletion_count
        
        deletion_count += 1

    return deletion_count

Big(O) Analysis

Time Complexity

O(n log n + m log m) – The GCD calculation of the m numbers in the second array numsDivide has a time complexity of O(m log m) where m is the size of numsDivide. Sorting the first array nums, which has a size of n, takes O(n log n). The iteration through the sorted first array nums to find the minimum number of deletions has a time complexity of O(n) but is dominated by the initial sorting. Therefore, the overall time complexity is O(n log n + m log m).

Space Complexity

O(1) – The space complexity is primarily determined by the calculation of the Greatest Common Divisor (GCD) and the sorting of the first array. The GCD calculation utilizes a constant amount of extra space. Sorting the first array is done in-place. Therefore, the auxiliary space used remains constant irrespective of the size of the input arrays, and no additional data structures that scale with the input size are created. The space usage does not grow with the input size.

Edge Cases

Case	How to Handle
nums is null or empty	Return -1 since no elements can be selected for divisibility.
numsDivide is null or empty	Return 0, as any smallest element from nums trivially divides an empty set.
nums contains negative numbers	The GCD or smallest element might be negative, so take the absolute value to ensure proper divisibility checks.
numsDivide contains negative numbers	Take the absolute value of numbers in numsDivide for divisibility checks.
nums contains zero	If the smallest element in nums is zero, return -1 as zero cannot divide any number.
numsDivide contains zero	The GCD of numsDivide will be zero; a valid smallest element from nums must be able to divide zero without issue, so find smallest element that works, or return -1 if none do.
No element in nums divides all elements in numsDivide	Return -1 because no solution is possible if no element in nums fulfills the divisibility condition.
nums contains duplicate values with varying frequencies	Count the occurrences of the smallest element(s) and handle deletions based on the smallest number and its frequency.

nums is null or empty

How to Handle:

Return -1 since no elements can be selected for divisibility.

numsDivide is null or empty

How to Handle:

Return 0, as any smallest element from nums trivially divides an empty set.

nums contains negative numbers

How to Handle:

The GCD or smallest element might be negative, so take the absolute value to ensure proper divisibility checks.

numsDivide contains negative numbers

How to Handle:

Take the absolute value of numbers in numsDivide for divisibility checks.

nums contains zero

How to Handle:

If the smallest element in nums is zero, return -1 as zero cannot divide any number.

numsDivide contains zero

How to Handle:

The GCD of numsDivide will be zero; a valid smallest element from nums must be able to divide zero without issue, so find smallest element that works, or return -1 if none do.

No element in nums divides all elements in numsDivide

How to Handle:

Return -1 because no solution is possible if no element in nums fulfills the divisibility condition.

nums contains duplicate values with varying frequencies

How to Handle:

Count the occurrences of the smallest element(s) and handle deletions based on the smallest number and its frequency.