Detailed and Easy Explanation of the O(n) solution
In this problem we are asked to delete the minimum length of subarray s.t. the remaining array sum is divisible by p. Following is the algorithm with proof of s
In this problem we are asked to delete the minimum length of subarray s.t. the remaining array sum is divisible by p. Following is the algorithm with proof of some tricky decisions. \n\n**step 1)**\n\ntake the sum of whole array. call it total. Then take the modulus of total with p. call it mod.\n\nmod  = total % p\n\nif mod is 0, then we can say that total is divisible by p and no need to delete any subarray. In that case our answer is 0. 0 elements needed to make array sum divisible by p.\n\nbut if the mod is non zero then we have to delete some subarray from the array. For this we can say that any minimum subarray that we want to remove must have modulus of its sum with p equal to mod. \n\nproof: \n\nsuppose we divide our whole array into 3 subarrays. \ns1,s2 and s3 means sum of respective subarrays\n\n\t_ _ _ s1 _ _ _  + _ _ _ s2 _ _ _ + _ _ _ s3 _ _ _  =  total\n\t\n\t\t(s1 + s2 + s3) % p = total % p = mod\n\t\t\n\t\tif s2%p == mod then \n\n\t\ts1 % p + mod  + s2 % p = mod\n\n\t\tso s1%p + s2%p == 0 which means it is divisible by p\n\t\t\n\t\t\nNow we need to find subarray s2 whose sum % p is mod\nfor this we have step 2 as following. \n\n**step2**\n\nwe can use 3 loops to find all the subarray sum and determine whose modulus with p is mod and which one\'s length is minimum also.  we can do it in two loops by using prefix sum trick. \nBut, \n\nhere is also O(n) solution with O(n) extra space. \nin this solution we need a unordered_map <int,int> to store prefixsum%p and its latest index i till which the prefix sum is considered. \n\ntrick is simply traverse the array and keep track of the prefixsum. call prefixsum at current index is ps. And keep storing the value of ps%p with its index i in the map. If at any index j , value of ps%p - mod is already present in the map with index i , we can say that j - i subarray sum % p == mod. And that could be our potential answer. \n\nproof. \n\t\tfollowing is the depiction of the array that can help to understand the concept. \n\t\tps1 is prefixsum till position i, ps2 is prefixsum till position j and ps is prefix sum between positon j and i. \n\n                        ps\n\t\t_ _ _ _ ps1 <--------> \n\t\n\t\t_ _ _ _ _ _ _ _ _ _ _ ps2\n\n\t\tps2%p - mod = ps1%p ---> (1)\n\t\t(ps1 + ps) % p - mod = ps1%p\n\t\tps1%p + ps%p - mod = ps1%p\n\t\tps%p = mod\n\n\t\tthis is what we wanted to find -> subarray with the modulus mod\n\t\t\n\t\t\n\t\t\n\nwe can keep going forward in the array and check for the minimum length of such subarray. \n\n**step3**\n\nnow when we are calculating ps%p-mod at any point, this value can be negative. And we always have our modulus value stored in map between 0 to p-1. To tackle the negative values, we can do something like following. \n\n(ps%p-mod+p)%p , adding p and then take mod of p. \n\n\t\tnow, adding p and taking a modulus with p does not change the original modulus \n\t\tthough negative modulus can be converted to postive which we wanted\n\t\tonly adding single time p can be sufficient to change value of modulus\n\t\tfrom negative to positive\n\nproof, \n\n\t\t\t_ _ _ _ _ _  ps%p\n\n\t\twe were taking mods of ps with p \n\t\tit\'s  value can be between 0 to p-1 always\n\n\t\tour total%p = mod value could be between 0 to p-1\n\n\t\tso ps%p - mod, its least value could be 0 - (p-1) which is 1 - p\n\n\t\tnow (1 - p + p)%p is 1 which the positive result when the most negative \n\t\tsituation we had , so adding p one time is sufficient\n\n\nPlease do comment for any doubt. \n\n\n\n\n\n\n\n\n\t\t\n\n
[]