Sponsored
Sponsored
This approach involves first calculating the remainder of the sum of the given array with respect to p. By maintaining a prefix sum and using the properties of modular arithmetic, we can determine the shortest subarray whose removal results in a remainder of zero.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for storing prefix sums in the hashmap.
1#include <vector>
2#include <unordered_map>
3#include <numeric>
4using namespace std;
5
6int minSubarray(vector<int>& nums, int p) {
7 int total_mod = accumulate(nums.begin(), nums.end(), 0) % p;
8 if (total_mod == 0) return 0;
9 unordered_map<int, int> prefix_map;
10 prefix_map[0] = -1;
11 int prefix_sum = 0, min_len = nums.size();
12 for (int i = 0; i < nums.size(); ++i) {
13 prefix_sum = (prefix_sum + nums[i]) % p;
14 int target = (prefix_sum - total_mod + p) % p;
15 if (prefix_map.find(target) != prefix_map.end()) {
16 min_len = min(min_len, i - prefix_map[target]);
17 }
18 prefix_map[prefix_sum] = i;
19 }
20 return min_len == nums.size() ? -1 : min_len;
21}This C++ solution uses the same logic as the Python solution, with an unordered_map to store prefix sums and find the minimum subarray length to remove for the desired remainder. Aggregating the numbers, modular arithmetic is used to achieve the desired check.
This approach makes use of a sliding window or two-pointer technique to identify the minimal subarray which upon removal makes the sum of the remaining elements divisible by p.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for maintaining the hashmap.
1function minSubarray(nums, p) {
2 letThis JavaScript implementation aligns with previous versions, utilizing an object to store prefix sums and applying similar logic to finalize the computation of the minimal subarray which satisfies the given condition.