Easy C++ Solution || Beat 100%
IntuitionThe problem revolves around removing the smallest subarray such that the sum of the remaining elements is divisible by p. The key insight is that divis
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem revolves around removing the smallest subarray such that the sum of the remaining elements is divisible by p. The key insight is that divisibility can be handled using modulo arithmetic, and instead of manually checking every possible subarray, we can leverage prefix sums and properties of modulo operations.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Modulo Target Calculation:**\nFirst, calculate the total sum of the array. If this sum is already divisible by p, we don\'t need to remove any subarray, so the answer is 0.\nIf the sum is not divisible by p, compute the target remainder (sum % p). This target remainder is the amount we need to "remove" (via a subarray) to make the rest of the sum divisible by p.\n\n**Prefix Sum and Modulo Arithmetic:**\nThe prefix sum up to any index i gives the sum of the elements from the beginning to that index. By calculating the prefix sum modulo p, we can check how much the cumulative sum is "off" from being divisible by p.\nIf at any index i, the prefix sum modulo p minus the target remainder appears earlier (in the hashmap), the difference between these two indices gives us a subarray that can be removed to make the remaining sum divisible by p.\n\n**Hashmap for Efficient Lookup:**\nTo efficiently find this subarray, maintain a hashmap mp that stores the most recent index where each prefix sum modulo p occurred. If we find a matching remainder (prefix[i] % p == prefix[j] % p for some j < i), the subarray between j and i is a candidate for removal.\nThe hashmap helps in tracking previous occurrences of modulo values, allowing constant time lookups.\n\n**Handle Negative Modulo Values:**\nWhen subtracting the target remainder from the current prefix sum modulo p, the result may be negative. To handle this, we add p and then take modulo p again, ensuring the result is always non-negative.\n\n**Minimizing the Subarray Length:**\nWhenever we find a valid subarray (i.e., the difference between the current prefix and the one stored in the hashmap), we update the answer with the minimum length of the subarray found.\n\n\n\n\n**\u2728 If this approach and code helped you, please don\u2019t forget to upvote!\nYour support keeps me motivated to share more such solutions and explanations. \uD83D\uDE0A\uD83D\uDE80**\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) \n    {\n        int n = nums.size();\n        long long sum = 0;\n        \n        // Calculate total sum of the array\n        for (int i = 0; i < n; i++) {\n            sum += nums[i];\n        }\n\n        // If the total sum is already divisible by p, return 0\n        if (sum % p == 0) return 0;\n\n        int target = sum % p;\n        unordered_map<int, int> mp;\n        mp[0] = -1;  // This handles the case when a prefix sum is divisible by p\n        long long prefix = 0;\n        int ans = n;\n\n        for (int i = 0; i < n; i++) {\n            prefix = (prefix + nums[i]) % p;\n\n            // Make sure prefix is positive (if it goes negative, add p)\n            int mod_value = (prefix - target + p) % p;\n            \n            // If we find the mod value in the map, update the answer\n            if (mp.find(mod_value) != mp.end()) {\n                ans = min(ans, i - mp[mod_value]);\n            }\n\n            // Store the current prefix modulo in the map\n            mp[prefix] = i;\n        }\n\n        // If no valid subarray is found, return -1\n        return (ans == n) ? -1 : ans;\n    }\n};\n\n```
['Array', 'Hash Table', 'Prefix Sum', 'C++']