C++ solution with intuition/explanation O(n)
Since there is \'subarray\' and \'sum\' involved, the intuitive first step is to find the prefix sum array.\nThe sum of all elements would be A[n-1].\nWe don\'t
Since there is \'subarray\' and \'sum\' involved, the intuitive first step is to find the prefix sum array.\nThe sum of all elements would be `A[n-1]`.\nWe don\'t want to deal with huge numbers, so we store everything `modulo p`.\n\nThe problem reduces to finding a subarray with sum (modulo p) = total sum (modulo p).\nSince we already have the prefix sum array, just find out the previous index j such that\n`(A[j+1] + ... + A[i]) % p = A[n-1] % p`.\nThis can be solved using a simple unordered map.\n\n***Complexity***\nTime `O(N)`\nSpace `O(N)`\n\n```\nint minSubarray(vector<int>& A, int p) {\n\tint n = A.size();        \n\tgetModularPrefixSum(A, n, p);\n\tif (A[n-1] == 0) return 0;  // The sum is already divisible by p\n\n\tint ans = n;\n\n\tunordered_map<int, int> prevIndex;\n\tprevIndex[0] = -1;          // If the subarray starts from the beginning\n\n\tfor (int i = 0; i < n; i++) {\n\t\tprevIndex[A[i]] = i;\n\t\tint diff = (A[i] - A[n-1] + p) % p;\n\n\t\tif (prevIndex.find(diff) != prevIndex.end())\n\t\t\tans = min(ans, i - prevIndex[diff]);\n\t}\n\n\treturn ans < n ? ans : -1;\n}\n\nvoid getModularPrefixSum(vector<int>& A, int n, int p) {\n\tA[0] %= p;\n\tfor (int i = 1; i < n; i++) {\n\t\tA[i] += A[i-1];\n\t\tA[i] %= p;\n\t}\n}\n```
['C', 'Prefix Sum']