LeetCode 2344: Minimum Deletions to Make Array Divisible Solution

Master LeetCode problem 2344 (Minimum Deletions to Make Array Divisible), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2344. Minimum Deletions to Make Array Divisible

Hard

Array Math Sorting Heap (Priority Queue)Number Theory

Problem Explanation

Explanation:

To solve this problem, we need to find the minimum number of deletions from the array nums such that the smallest element in nums divides all the elements in array numsDivide.

We first find the smallest element in nums.
Then, we iterate over all the elements in numsDivide and check if the smallest element in nums can divide each element in numsDivide.
If the smallest element in nums can divide all elements in numsDivide, we return 0 as no deletions are needed.
If not, we try deleting elements equal to the smallest element in nums one by one and check if the modified nums array can divide all elements in numsDivide.
We keep track of the minimum number of deletions required to make nums divisible by all elements in numsDivide.

Time Complexity: O(N) where N is the size of the input arrays nums and numsDivide.

Space Complexity: O(1)

Solution Code

class Solution {
    public int minDeletions(int[] nums, int[] numsDivide) {
        int minElement = Integer.MAX_VALUE;
        for (int num : nums) {
            minElement = Math.min(minElement, num);
        }
        
        for (int i = 0; i < numsDivide.length; i++) {
            if (numsDivide[i] % minElement != 0) {
                int deletions = 0;
                for (int j = 0; j < nums.length; j++) {
                    if (nums[j] == minElement) {
                        deletions++;
                        nums[j] = 0;
                        if (canDivide(nums, numsDivide)) {
                            return deletions;
                        }
                    }
                }
            }
        }
        
        return -1;
    }
    
    private boolean canDivide(int[] nums, int[] numsDivide) {
        int minElement = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num != 0) {
                minElement = Math.min(minElement, num);
            }
        }
        
        for (int i = 0; i < numsDivide.length; i++) {
            if (numsDivide[i] % minElement != 0) {
                return false;
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2344 (Minimum Deletions to Make Array Divisible)?

This page provides optimized solutions for LeetCode problem 2344 (Minimum Deletions to Make Array Divisible) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2344 (Minimum Deletions to Make Array Divisible)?

The time complexity for LeetCode 2344 (Minimum Deletions to Make Array Divisible) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2344 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2344 in Java, C++, or Python.

Back to LeetCode Solutions