2344. Minimum Deletions to Make Array Divisible

Time: O(m log m + n log n)

Space: O(1)

Intuition

Count minimum operations to make each array element <= limit. Each op reduces an element. Elements > limit need ceiling(excess/dec) ops.

Algorithm

1For each value > limit: count occurrences. Ops = sum of occurrences rounded up based on decrement value.

Common Pitfalls

•Operations apply to groups of elements. Batch reductions with counting sort.

2344.cs

// Approach: GCD of numsDivide; sort nums; count how many elements don't divide the GCD.
// Time: O(m log m + n log n) Space: O(1)

public class Solution
{
    public int MinOperations(int[] nums, int[] numsDivide)
    {
        int gcd = GetGCD(numsDivide);

        Array.Sort(nums);

        for (int i = 0; i < nums.Length; ++i)
        {
            if (gcd % nums[i] == 0)
                return i;
        }

        return -1;
    }

    private int GetGCD(int[] nums)
    {
        int g = nums[0];
        foreach (int num in nums)
            g = Gcd(g, num);
        return g;
    }

    private int Gcd(int a, int b)
    {
        return b == 0 ? a : Gcd(b, a % b);
    }
}

Was this solution helpful?