Optimized Subarray Removal to Achieve Divisibility || C++
Intuition\n Describe your first thoughts on how to solve this problem. \n- The problem is to find the smallest subarray such that removing it makes the sum of t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- The problem is to find the smallest subarray such that removing it makes the sum of the remaining elements divisible by p. This can be solved using modular arithmetic. The sum of the array modulo p gives the remainder when divided by p. If the remainder is 0, then the sum is already divisible by p. Otherwise, we need to find the smallest subarray whose sum has the same remainder modulo p as the difference between the total sum and the nearest multiple of p.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Calculate the total sum of the array and compute the target remainder, target = total_sum % p. We want to remove a subarray whose sum has this remainder modulo p to make the remaining sum divisible by p.\n- Use a hash map to keep track of the prefix sum remainders (modulo p) encountered during traversal. This helps us find if there\'s any prefix that can be removed to achieve the target remainder.\n- Traverse the array and maintain a running sum of the elements. For each index, compute the current remainder modulo p and check if we have previously encountered a remainder that would allow the current subarray to achieve the desired target.\n- Update the minimum subarray length whenever a valid subarray is found.\n- Return the minimum length found or -1 if no such subarray exists.\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        long long int total_sum = 0;\n        for (auto& num : nums) {\n            total_sum += num; \n        }\n        if(p >  total_sum) {\n            return -1;\n        }\n        long long int target = total_sum % p;\n\n        if(target == 0) {\n            return 0;\n        }\n\n        unordered_map<int, int> mp;\n        mp[0] = -1; \n        long long int cur_sum = 0;\n        int mini = nums.size();\n\n        for (int i = 0; i < nums.size(); i++) {\n            cur_sum += nums[i];\n            int cur_rem = cur_sum % p;\n            int rem = (cur_rem - target + p) % p;\n\n            if (mp.find(rem) != mp.end()) {\n                int sub = i - mp[rem];\n                mini = min(mini, sub);\n            }\n\n            mp[cur_rem] = i;\n        }\n\n        return mini == nums.size() ? -1 : mini;\n    }\n};\n\n```
['C++']