Minimum Deletions to Make Array Divisible

Minimum Deletions to Make Array Divisible - Problem

Array Math Sorting Heap (Priority Queue) Number Theory Hard

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: An integer x divides y if y % x == 0.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,2,4,6,7,4], numsDivide = [9,3,12,6]

› Output: 2

💡 Note: We need to find the smallest element in nums that divides all elements in numsDivide. After sorting nums = [2,2,3,4,4,6,7], we test: 2 doesn't divide 9, but 3 divides all elements (9÷3=3, 3÷3=1, 12÷3=4, 6÷3=2). Since 3 is at index 2 in sorted array, we need 2 deletions.

Example 2 — No Solution

$ Input: nums = [7,21,14], numsDivide = [5,10,15]

› Output: -1

💡 Note: No element in nums can divide all elements in numsDivide. For example, 7 doesn't divide 5 (5÷7 has remainder), 14 doesn't divide 5, and 21 doesn't divide 5. Since no valid divisor exists, return -1.

Example 3 — First Element Works

$ Input: nums = [1,2,3], numsDivide = [2,4,6]

› Output: 0

💡 Note: The smallest element 1 divides all elements in numsDivide (2÷1=2, 4÷1=4, 6÷1=6). Since 1 is already the smallest, no deletions needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums array to modify and numsDivide array as targets

Find Target

Calculate what the divisor needs to be (GCD of numsDivide)

Count Deletions

Sort nums and find first valid element

Key Takeaway

🎯 Key Insight: Use GCD to determine the target divisor - any element that divides all numbers must also divide their GCD

Asked in

G Google 15 f Meta 8

The key insight is that any divisor of all elements in numsDivide must also divide their GCD. Best approach computes GCD of numsDivide, sorts nums, then finds the first element that divides the GCD. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Elements	O(n log n + n × m)	O(1)	Sort nums and test each element to see if it divides all elements in numsDivide
Mathematical Optimization using GCD	O(n log n + m log(max(numsDivide)))	O(1)	Use GCD of numsDivide to determine the target divisor, then find smallest valid element in nums

Brute Force - Try All Elements — Algorithm Steps

Sort nums array in ascending order
For each element in sorted nums, check if it divides all elements in numsDivide
Return the index (number of deletions) when we find a valid divisor

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort nums

Arrange elements from smallest to largest

Test each element

Check if current element divides all numsDivide elements

Return count

Number of elements to delete when valid divisor found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int* numsDivide, int numsDivideSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    
    for (int i = 0; i < numsSize; i++) {
        int current = nums[i];
        int canDivideAll = 1;
        
        for (int j = 0; j < numsDivideSize; j++) {
            if (numsDivide[j] % current != 0) {
                canDivideAll = 0;
                break;
            }
        }
        
        if (canDivideAll) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int nums[1000];
    int numsSize = 0;
    char *token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse second array
    int numsDivide[1000];
    int numsDivideSize = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            numsDivide[numsDivideSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, numsSize, numsDivide, numsDivideSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n × m)

O(n log n) for sorting nums, then O(n × m) for checking each element against all numsDivide elements

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

21.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Elements — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler