Detailed explanation of algo + code (c++) || prefix sum
we want to make sum divisible by p :-\n1. Calculate total sum of array \n\ta. if sum already divisible by p , return 0 \n\tb. calculate remainder ( rem = total_
we want to make sum divisible by p :-\n1. Calculate total sum of array \n\ta. if sum already divisible by p , return 0 \n\tb. calculate remainder ( rem = total_sum % p )\n2. Now we need to find smallest subarray which gives remainder \'rem\' on division by p\n3. To find such subarray we\'ll use prefix sum array % p \n4. idea behind step 3 is -> if ( S1 - S2 )%p = rem then subarray between S1 and S2 is our desried array \n5. to handle negative result of (S1-S2) cases we will add \'p\' to result of (S1-S2)%p \n6. Conclusion - on prefix sum array look for 3 things \n\ta. element = nums[i]-rem \n\tb. element = nums[i]+k-rem (for negative case)\n\tc. if current element in prefix sum array = rem only \n7. if final length calculated = INT_MAX (initial set value) or = length of nums , then return -1 , otherwise ans .\n\nCode - \n``` \nint minSubarray(vector<int>& arr, int p) {\n        int sum = 0 ;\n        int n = arr.size() ;\n        \n        for(int i=0 ; i<n ; i++){\n            sum= (sum + arr[i])%p ;\n\t\t\t// take %p so that sum does not go out of int range\n        }\n        \n        int rem = sum%p ; \n\t\t\n        if(rem==0) return 0 ; // if rem=0 , array already divisible by p return 0 \n        \n\t\t// build prefix sum array % p \n\t\t\n        for(int i=1 ; i<n ; i++){\n\t        arr[i] = (arr[i] + arr[i-1])%p ;\n\t    }\n\t    \n\t    map<int,int> mp ; // map to find our desired 3 things\n\t\t\n\t    int ans = INT_MAX ;\n\t    \n\t    for(int i=0 ; i<n ; i++){\n            \n            int req1 = arr[i]-rem ; \n            int req2 = arr[i]+p-rem ; // for negative cases\n            \n\t\t\t// currans denotes length of desired subarray\n\t\t\t\n\t        if( mp.count(req1) ){\n                int currans = i-mp[req1] ;\n                ans=min(ans,currans) ;\n                \n            }else if(mp.count(req2)){\n                int currans = i-mp[req2] ;\n                ans=min(ans,currans) ;\n                \n            }else if(arr[i]==rem){\n\t\t\t\t// if curr element is equal to rem , this means subarray from 0th index to this index is our desired subarray\n                int currans = i+1 ;\n                ans=min(ans,currans) ;\n               \n            }\n            \n            mp[arr[i]] = i ;\n\t    }\n\t    \n        if(ans==INT_MAX || ans==n) return -1 ;\n\t\t// return -1 if whole array or no subarray is our ans \n\n        return ans ;\n\n    }\n```
[]