C++; O(n) with explanation
Here store a postsum array with modulus first.\nNext we traverse the array in presum manner and store the position of presums in the map.\nThe numbers we are lo
Here store a postsum array with modulus first.\nNext we traverse the array in presum manner and store the position of presums in the map.\nThe numbers we are looking for should be in a complement manner w.r.t the moldulus number.\nEg. - Let say we have p = 6.\nSo if at any position i, if we have postsum modulus = 2, and if we are able to find a presum modulus of 4, then we can say that we can remove the subarray between last occurance of 4 and current position i.\nThe rest is intuitive.\n```\nint minSubarray(vector<int>& nums, int p) {\n        unordered_map<long long,int> mp;\n        int n = nums.size();\n        int mini = INT_MAX;\n        long long curr = 0;\n        \n        vector<int> postsum(n,0);\n        postsum[n-1] = nums[n-1]%p;\n        for(int i=n-2;i>=0;i--)\n        {\n            postsum[i] = (postsum[i+1] + nums[i])%p;\n            if(postsum[i] == 0) mini = min(mini,i);\n        }\n        \n        mp[0] = -1;\n        for(int i=0;i<nums.size();i++)\n        {\n            curr = (curr + nums[i])%p;\n            if(curr==0)\n                mini = min(mini,n-i-1);\n            if(mp.find(p-postsum[i])!=mp.end())\n                mini = min(mini,i-mp[p-postsum[i]]-1);\n            mp[curr] = i;\n        }\n        return mini==INT_MAX?-1:mini;\n    }\n```
[]