Java PrefixSum With HashMap With Detailed Explanation and comments
Intuition\n_________\n1.Which subarray we need to remove so that remaining sum % p == 0?\n-> If (subarray sum from (0,i) + subarray sum from (j,n) ) % p == 0 th
Intuition\n_________________________________________________________\n1.Which subarray we need to remove so that remaining sum % p == 0?\n-> If (subarray sum from (0,i) + subarray sum from (j,n) ) % p == 0 then we should remove(i+1,j-1)\n2. How to find i and j value?\n-> let\'s say sum of (0,i) % p =x  and sum of(j,n) % p = p-x then these subarray sum % p = 0\ne.g -> (1+2+3) % 5 = 1 \n(6+3) % 5 = 4 then (1+2+3+6+3) % 5 = 0.\n\n```\nclass Solution {\n    public int minSubarray(int[] nums, int p) {\n        int n = nums.length;\n        long[] ps= new long[n+1];\n        for(int i=1;i<=n;i++){\n            ps[i] =ps[i-1]+nums[i-1];\n        }\n        long rem = ps[n] % p;\n        if(rem == 0) return 0;\n        Map<Long,Integer> map = new HashMap<>();\n        map.put(0l,n+1);\n        int ans = n;\n        long sum = 0;\n        for(int i=n;i>=0;i--){\n\t\t\t// x value\n            long reminder = ps[i] % p;\n\t\t\t// p-x value\n            long required = reminder == 0?0:p-reminder;\n\t\t\t// calculate length\n            if(map.containsKey(required)) ans = Math.min(ans,map.get(required) - i-1);\n\t\t\t// prefix sum from right\n            if(i>0)sum+=nums[i-1];\n            map.put(sum % p,i);\n            \n        }\n        return ans == n?-1:ans;\n        \n    }\n}\n```\n
['Prefix Sum', 'Java']