🌟 Fastest Way to Make Sum Divisible by P in Multiple Languages 💯🔥
\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step app
![Screenshot 2024-07-02 113653.png](https://assets.leetcode.com/users/images/7262be7d-bf8e-4f45-b1df-1b7eb5282609_1727915283.296274.png)\n\nExplore a collection of solutions to LeetCode problems in multiple programming languages. Each solution includes a detailed explanation and step-by-step approach to solving the problem efficiently. Whether you\'re a beginner looking to learn or an experienced coder seeking optimized solutions, this repository aims to provide clear and insightful approaches to tackling challenging LeetCode problems.\n\n### **Access daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/cee7e519-c082-4558-82a7-2554657b5658_1727915231.1635237.png)\n\n---\n\n# Intuition\nThe problem asks us to remove the smallest subarray such that the sum of the remaining elements is divisible by a given integer `p`. Our key observation is that the total sum of the array determines how much we need to adjust. We want to remove a subarray whose sum has a specific remainder when divided by `p`.\n\nIf we can efficiently find a subarray whose sum mod `p` equals the needed remainder, we can solve the problem optimally.\n\n---\n\n# Approach\n1. **Total Sum Calculation**: First, calculate the total sum of the array and its remainder when divided by `p`.\n2. **Target Subarray**: We need to remove a subarray such that the sum of the remaining elements is divisible by `p`. The sum of the removed subarray should have the same remainder as the total sum mod `p`.\n3. **Prefix Sums**: We utilize prefix sums to track the sum of subarrays. By keeping track of the prefix sums mod `p`, we can check if a subarray that satisfies the condition can be found.\n4. **Optimization with Hashmap**: We use a hashmap to store the prefix sum modulo values, which helps in quickly finding a valid subarray by comparing remainders.\n\n---\n\n# Complexity\n\n- **Time complexity**:  \n  $$O(n)$$, where \\(n\\) is the number of elements in the `nums` array. We only need to traverse the array once, and each operation (including the hashmap lookup) takes constant time.\n\n- **Space complexity**:  \n  $$O(n)$$ because we store prefix sums in a hashmap, and in the worst case, we might store up to \\(n\\) entries.\n\n---\n\n# Code\n```C++ []\n#include <vector>\n#include <unordered_map>\nusing namespace std;\n\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        long totalSum = 0;\n        for (int num : nums) {\n            totalSum += num;\n        }\n\n        // Find the remainder when total sum is divided by p\n        int rem = totalSum % p;\n        if (rem == 0) return 0; // If the remainder is 0, no subarray needs to be removed\n\n        unordered_map<int, int> prefixMod;\n        prefixMod[0] = -1;  // Initialize for handling full prefix\n        long prefixSum = 0;\n        int minLength = nums.size();\n\n        for (int i = 0; i < nums.size(); ++i) {\n            prefixSum += nums[i];\n            int currentMod = prefixSum % p;\n            int targetMod = (currentMod - rem + p) % p;\n\n            if (prefixMod.find(targetMod) != prefixMod.end()) {\n                minLength = min(minLength, i - prefixMod[targetMod]);\n            }\n\n            prefixMod[currentMod] = i;\n        }\n\n        return minLength == nums.size() ? -1 : minLength;\n    }\n};\n\n```\n```Java []\nimport java.util.HashMap;\n\nclass Solution {\n    public int minSubarray(int[] nums, int p) {\n        long totalSum = 0;\n        for (int num : nums) {\n            totalSum += num;\n        }\n\n        // Find remainder when total sum is divided by p\n        int rem = (int)(totalSum % p);\n        if (rem == 0) return 0; // If remainder is 0, no subarray needs to be removed\n\n        HashMap<Integer, Integer> prefixMod = new HashMap<>();\n        prefixMod.put(0, -1);  // Initialize to handle full prefix\n        long prefixSum = 0;\n        int minLength = nums.length;\n\n        for (int i = 0; i < nums.length; ++i) {\n            prefixSum += nums[i];\n            int currentMod = (int)(prefixSum % p);\n            int targetMod = (currentMod - rem + p) % p;\n\n            if (prefixMod.containsKey(targetMod)) {\n                minLength = Math.min(minLength, i - prefixMod.get(targetMod));\n            }\n\n            prefixMod.put(currentMod, i);\n        }\n\n        return minLength == nums.length ? -1 : minLength;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} p\n * @return {number}\n */\nvar minSubarray = function(nums, p) {\n    let totalSum = nums.reduce((a, b) => a + b, 0);\n\n    // Find the remainder when total sum is divided by p\n    let rem = totalSum % p;\n    if (rem === 0) return 0;  // If the remainder is 0, no subarray needs to be removed\n\n    let prefixMod = new Map();\n    prefixMod.set(0, -1);  // Initialize to handle full prefix\n    let prefixSum = 0;\n    let minLength = nums.length;\n\n    for (let i = 0; i < nums.length; i++) {\n        prefixSum += nums[i];\n        let currentMod = prefixSum % p;\n        let targetMod = (currentMod - rem + p) % p;\n\n        if (prefixMod.has(targetMod)) {\n            minLength = Math.min(minLength, i - prefixMod.get(targetMod));\n        }\n\n        prefixMod.set(currentMod, i);\n    }\n\n    return minLength === nums.length ? -1 : minLength;\n};\n\n```\n```Python []\nclass Solution:\n    def minSubarray(self, nums: List[int], p: int) -> int:\n        totalSum = sum(nums)\n        rem = totalSum % p\n\n        if rem == 0:\n            return 0\n\n        prefixMod = {0: -1}\n        prefixSum = 0\n        minLength = len(nums)\n\n        for i, num in enumerate(nums):\n            prefixSum += num\n            currentMod = prefixSum % p\n            targetMod = (currentMod - rem + p) % p\n\n            if targetMod in prefixMod:\n                minLength = min(minLength, i - prefixMod[targetMod])\n\n            prefixMod[currentMod] = i\n\n        return minLength if minLength < len(nums) else -1\n\n```\n```Go []\nfunc minSubarray(nums []int, p int) int {\n    totalSum := 0\n    for _, num := range nums {\n        totalSum += num\n    }\n\n    rem := totalSum % p\n    if rem == 0 {\n        return 0\n    }\n\n    prefixMod := make(map[int]int)\n    prefixMod[0] = -1\n    prefixSum, minLength := 0, len(nums)\n\n    for i, num := range nums {\n        prefixSum += num\n        currentMod := prefixSum % p\n        targetMod := (currentMod - rem + p) % p\n\n        if idx, ok := prefixMod[targetMod]; ok {\n            if i-idx < minLength {\n                minLength = i - idx\n            }\n        }\n\n        prefixMod[currentMod] = i\n    }\n\n    if minLength == len(nums) {\n        return -1\n    }\n    return minLength\n}\n\n```\n\n---\n\n# Step-by-Step Detailed Explanation\n\n1. **Total Sum Calculation**:\n   - The total sum of the array is calculated to determine the remainder when divided by `p`.\n   - Example: For `nums = [3, 1, 4, 2]`, the total sum is `10`, and `10 % 6 = 4`.\n\n2. **Check if No Subarray is Needed**:\n   - If the remainder is `0`, no subarray needs to be removed, and we return `0` immediately.\n\n3. **Prefix Sum with Modulo**:\n   - As we iterate over the array, we calculate the prefix sum modulo `p` for each index.\n   - We store these modulo values in a hashmap for quick lookup. This helps us check if a previous prefix sum matches the required condition.\n\n4. **Efficient Subarray Removal**:\n   - For each element, we check if there exists a prefix sum modulo `p` that, when combined with the current prefix sum, would remove a subarray whose sum has the same remainder as `rem`.\n   - The hashmap allows us to do this efficiently by storing the indices of the prefix sums.\n\n5. **Return Result**:\n   - After the loop, we return the minimum length of the subarray found, or `-1` if no valid subarray exists.\n\n---\n\n# Visualization\n\nLet\u2019s take **Example 1**: \n\n```plaintext\nnums = [3, 1, 4, 2], p = 6\n```\n\n1. **Total Sum Calculation**:  \n   First, we calculate the sum of the entire array:\n\n   ```\n   3 + 1 + 4 + 2 = 10\n   ```\n\n2. **Remainder Check**:  \n   Find the remainder when the total sum is divided by `p`:\n\n   ```\n   10 % 6 = 4\n   ```\n\n   Since the remainder is `4`, the total sum is not divisible by `6`. This means we need to remove a subarray that will adjust this remainder to `0`.\n\n3. **Target Remainder for Subarray**:  \n   We want to remove a subarray whose sum mod `6` equals `4`. This will leave a sum divisible by `6` for the remaining elements.\n\n4. **Subarray Visualization**:  \n   One possible subarray we can remove is `[4]`. Removing this gives us the remaining elements `[3, 1, 2]`:\n\n   ```\n   3 + 1 + 2 = 6\n   ```\n\n   Now, `6 % 6 = 0`, which satisfies the condition.\n\n5. **Optimal Subarray**:  \n   The subarray `[4]` is of length `1`, which is the smallest subarray we can remove.\n\nHere\u2019s a visual representation of this approach:\n\n```plaintext\nInitial Array: [3, 1, 4, 2]\nTotal Sum: 10\nRemainder (10 % 6): 4\nTarget Subarray Sum (mod 6 = 4): [4]\nRemaining Elements after Removal: [3, 1, 2]\nRemaining Sum: 6\nResult: Length of Subarray to Remove = 1\n```\n\n---\n\n![upvote cat.png](https://assets.leetcode.com/users/images/2db61647-affc-4700-b7f6-882916eeb134_1727915501.741716.png)\n
['Array', 'Hash Table', 'Prefix Sum', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']