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.
1import java.util.*;
2
3The Java solution uses a HashMap to keep track of prefix sums as keys, linked to their indexes. The final loop computes prefix sums iteratively and checks for the desired remainder, computing the minimal subarray, if applicable.