🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n\n---\n\n# Intuition\nWe want to remove the shortest subarray from the array such that the sum of the remaining elements is divisible by p. This can be tran
![image.png](https://assets.leetcode.com/users/images/167f3ce2-09d3-424c-bc19-216481eacf5a_1727940603.437879.png)\n\n\n---\n\n# Intuition\nWe want to remove the shortest subarray from the array such that the sum of the remaining elements is divisible by `p`. This can be translated to finding the smallest subarray whose sum has a remainder that, when removed, leaves the total sum divisible by `p`.\n\n---\n\n# Approach\n1. Calculate the total sum of the array and determine the remainder when this sum is divided by `p`. We need to remove a subarray whose sum gives this remainder.\n2. Use a prefix sum approach to track cumulative sums modulo `p`. This helps us to find a subarray that, when removed, results in a sum divisible by `p`.\n3. Use a hashmap to store the prefix sums and their indices, allowing us to look up subarrays quickly.\n\n---\n\n# Complexity\n- **Time Complexity**: \\(O(n)\\), where \\(n\\) is the number of elements in the array, as we process each element once.\n- **Space Complexity**: \\(O(n)\\), for storing prefix sums in a hashmap.\n\n---\n\n```dart []\nclass Solution {\n  int minSubarray(List<int> nums, int p) {\n    int totalSum = nums.reduce((a, b) => a + b);\n    int req = totalSum % p;\n\n    if (req == 0) return 0;\n\n    Map<int, int> prefixMap = {0: -1};\n    int prefixSum = 0;\n    int minLength = nums.length;\n\n    for (int i = 0; i < nums.length; i++) {\n      prefixSum = (prefixSum + nums[i]) % p;\n      int target = (prefixSum - req) % p;\n      if (target < 0) target += p;\n\n      if (prefixMap.containsKey(target)) {\n        minLength = min(minLength, i - prefixMap[target]!);\n      }\n\n      prefixMap[prefixSum] = i;\n    }\n\n    return minLength == nums.length ? -1 : minLength;\n  }\n}\n```\n\n```c []\n#include <stdio.h>\n#include <stdlib.h>\n#include <limits.h>\n\nint minSubarray(int* nums, int numsSize, int p) {\n    int totalSum = 0;\n    for (int i = 0; i < numsSize; i++) {\n        totalSum += nums[i];\n    }\n\n    int req = totalSum % p;\n    if (req == 0) return 0;\n\n    int* prefixMap = (int*)calloc(p, sizeof(int));\n    for (int i = 0; i < p; i++) prefixMap[i] = -1;\n\n    prefixMap[0] = -1;\n    int prefixSum = 0;\n    int minLength = numsSize;\n\n    for (int i = 0; i < numsSize; i++) {\n        prefixSum = (prefixSum + nums[i]) % p;\n        int target = (prefixSum - req + p) % p;\n\n        if (prefixMap[target] != -1) {\n            minLength = (i - prefixMap[target]) < minLength ? (i - prefixMap[target]) : minLength;\n        }\n\n        prefixMap[prefixSum] = i;\n    }\n\n    free(prefixMap);\n    return minLength == numsSize ? -1 : minLength;\n}\n```\n\n```cpp []\n#include <vector>\n#include <unordered_map>\n#include <algorithm>\n\nclass Solution {\npublic:\n    int minSubarray(std::vector<int>& nums, int p) {\n        int totalSum = 0;\n        for (int num : nums) totalSum += num;\n        \n        int req = totalSum % p;\n        if (req == 0) return 0;\n\n        std::unordered_map<int, int> prefixMap;\n        prefixMap[0] = -1;\n\n        int prefixSum = 0;\n        int minLength = nums.size();\n\n        for (int i = 0; i < nums.size(); i++) {\n            prefixSum = (prefixSum + nums[i]) % p;\n            int target = (prefixSum - req + p) % p;\n\n            if (prefixMap.find(target) != prefixMap.end()) {\n                minLength = std::min(minLength, i - prefixMap[target]);\n            }\n\n            prefixMap[prefixSum] = i;\n        }\n\n        return minLength == nums.size() ? -1 : minLength;\n    }\n};\n```\n\n```java []\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass Solution {\n    public int minSubarray(int[] nums, int p) {\n        int totalSum = 0;\n        for (int num : nums) totalSum += num;\n\n        int req = totalSum % p;\n        if (req == 0) return 0;\n\n        Map<Integer, Integer> prefixMap = new HashMap<>();\n        prefixMap.put(0, -1);\n\n        int prefixSum = 0;\n        int minLength = nums.length;\n\n        for (int i = 0; i < nums.length; i++) {\n            prefixSum = (prefixSum + nums[i]) % p;\n            int target = (prefixSum - req + p) % p;\n\n            if (prefixMap.containsKey(target)) {\n                minLength = Math.min(minLength, i - prefixMap.get(target));\n            }\n\n            prefixMap.put(prefixSum, i);\n        }\n\n        return minLength == nums.length ? -1 : minLength;\n    }\n}\n```\n\n```javascript []\nvar minSubarray = function(nums, p) {\n    const totalSum = nums.reduce((a, b) => a + b, 0);\n    const req = totalSum % p;\n\n    if (req === 0) return 0;\n\n    const prefixMap = new Map();\n    prefixMap.set(0, -1);\n\n    let prefixSum = 0;\n    let minLength = nums.length;\n\n    for (let i = 0; i < nums.length; i++) {\n        prefixSum = (prefixSum + nums[i]) % p;\n        const target = (prefixSum - req + p) % p;\n\n        if (prefixMap.has(target)) {\n            minLength = Math.min(minLength, i - prefixMap.get(target));\n        }\n\n        prefixMap.set(prefixSum, 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        req = totalSum % p\n\n        if req == 0:\n            return 0\n\n        prefixMap = {0: -1}\n        prefixSum = 0\n        minLength = len(nums)\n\n        for i, num in enumerate(nums):\n            prefixSum = (prefixSum + num) % p\n            target = (prefixSum - req + p) % p\n\n            if target in prefixMap:\n                minLength = min(minLength, i - prefixMap[target])\n\n            prefixMap[prefixSum] = 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    req := totalSum % p\n    if req == 0 {\n        return 0\n    }\n\n    prefixMap := map[int]int{0: -1}\n    prefixSum := 0\n    minLength := len(nums)\n\n    for i, num := range nums {\n        prefixSum = (prefixSum + num) % p\n        target := (prefixSum - req + p) % p\n\n        if val, exists := prefixMap[target]; exists {\n            if i-val < minLength {\n                minLength = i - val\n            }\n        }\n\n        prefixMap[prefixSum] = i\n    }\n\n    if minLength == len(nums) {\n        return -1\n    }\n\n    return minLength\n}\n```\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}*C**, **C++**, **Java**, **JavaScript**, **Python**, and **Go**.
['Array', 'Hash Table', 'C', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']