C++ O(N) solution with prefix sum approach
To be honest I got this solution intuitively. But this idea worked out. So, here it is:\n\nLet\'s name sum of all elements of array total_sum. So,\ntotal_sum % 
To be honest I got this solution intuitively. But this idea worked out. So, here it is:\n\nLet\'s name sum of all elements of array total_sum. So,\n`total_sum % p = r` (if `r == 0`, this is fine. We do not need to remove subarrays)\nLet\'s consider `r > 0` case. \n`total_sum % p = (subsum_we_need + extra_subsum) % p = subsum_we_need % p + extra_subsum % p = 0 + extra_subsum % p = extra_subsum % p`, i.e, we are looking for such subarray with such sum, the rest of which equals to `total_sum % p`.\n\n3 1 **4** 2, k = 6, because (3 + 1 + 4 + 2) % 6 = 4  \n6 3 **5 2**, k = 9, because (6 + 3 + 5 + 2) % 9 = 7\n**8 32 31 18 34 20 21** 13 1 27 23 22 11 15 30 4 2, k = 148, because (8 + 32 + ... + 2) % 148 = 16\n\nSo, the main goal is to look for **a subsum that gives the required rest**.\nWe are going to use prefix sum but how do we know that there is a smaller needed subarray?\nLet\'s consider this:\n\n`3 1 4 2`\n\n1. `(3 + 1) % 6 -> 4`. We can consider this subarray of length `2`, because it gives the rest `4`. But can we look for shorter subarray further? Let\'s remember the last index of (3 + 1) prefix sum in map-cotainer `m[ sum % p ] = i;`\n2. `(3 + 1 + 4) % 6 -> 4`. Either `(3 + 1)` or `4` gives `4` as the rest. So what?\nLet\'s subtract `4` (the given rest) from this sum: `3 + 1 + 4 - 4 = 3 + 1`. Why have we just subtracted `4` from this prefix sum? How can this help us? Actually, this subtraction helps us to understand whether the current sum contains new coming "sub-sub"-sum that also gives the rest `4`.\nFor, example, let\'s consider the such case" \n`3 + 1 + 2 -> (3 + 1 + 2 - 4) % 6-> (4 - 2) % 6 -> 2 % 6 --- we have not met that`  \nbut with\n `3 + 1 + 4 -> (3 + 1 + 4 - 4) % 6 -> (3 + 1) % 6 + (4 - 4) % 6 -> (3 + 1) % 6 --- we have already considered this before`.\nLook at 1 paragraph -- we remembered `(3 + 1)` index. Let\'s calculate the length of new coming "sub-sub"-sum `4`:\n```\nlong long subtracted = sum - rest; // 3  + 1 + 4 - 4\nlong long r = subtracted % p; // (3 + 1) % 6\nint sub_sub_sum_length = i - m[r]; // current_index - m[already_gotten_rest]\n```\n\nThe entire code\n```\nclass Solution {\npublic:\n    int minSubarray(const std::vector<int>& nums, int p) {\n        long long sum = 0;\n        long long N = nums.size();\n\n        std::map<long long, long long> m;\n\n        long long total_sum = 0;\n\n        for (long long num : nums) {\n            total_sum += num % p;\n        }\n\n        if (total_sum % p == 0) {\n            return 0;\n        }\n\n        long long rest = total_sum % p;\n\n        long long ans = INT32_MAX;\n\n        for (long long i = 0; i < N; ++i) {\n            sum += nums[i];\n\n            long long subtracted = sum - rest;\n            long long r = subtracted % p;\n\n            if (m.count(r)) {\n                ans = std::min(ans, i - m[r]);\n            } \n\n            if (r == 0) {\n                ans = std::min(ans, i + 1);\n            }\n\n            m[ sum % p ] = i;\n        }\n\n        if (ans == INT32_MAX || ans == nums.size()) {\n            return -1;\n        }\n\n        return ans;\n    }\n};\n```  \n
[]