Simple and Clean Solution in Java with Detailed Explanation (Faster than 86.60%)
Vote Up if You Like it :)\n\nWarm up:\n1. It\'s a variation of problems which ask you to find a continous subarray that have a sum divisible by K. (I strongly s
Vote Up if You Like it :)\n\nWarm up:\n1. It\'s a variation of problems which ask you to find a continous subarray that have a sum divisible by K. (I strongly suggest that you should solve problem 523/974 before step into this problem)\n2. This problem asks you to remove a smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. The first idea in you head may transform the problem into something like "Find the longest subarray with sum divisible by p". However, the tricky and interesting part in this problem is that the remaining part after the remove operation may not be continous (See example 1: nums = [3,1,4,2], p = 6). So, such kind of tranformation will not work.\n3. Only the subarray which will be removed in this problem is continous. So, we need to make full use of this point.\n\nDeep dive\n1. If you are able to solve problem 523/974. The lesson which you learned is that given an array [n1...,  n2...] with sum % p = R. If there is a subarray with sum which is divisible by p, then the sum of remaining parts must % p = R. In other words, if there is a subarray with sum % p = R, then the sum of remaining parts must be divisble by p.\n2. In this problem, we need to remove a subarray so that the sum of remaining part is divisble by p. If the sum of the entire array % p = R, then we know the sum of the \'to be removed\' subarray % p = R.  \n3. So, we are able to **transform the problem into "Find the shortest subarray with sum % p = R. (R = SumOfEntireArray % p)**"\n4. Now, we can start to code like problem 523/974. We will use a HashMap to store each cumulative sum % p and its right most index. Also, **the target remainder which we need to check in HashMap is: sum % p - R**.\n\nSome edge cases you may need to pay attention when coding\n1. The sum of all elements in the array may overflow\n2. The sum of all elements < p (You will never find a solution)\n3. The sum of all elements % p == 0. (You don\'t need to remove any element)\n4. It is not allowed to remove the whole array\n5. and so on...\n\n\n\n\n\t\tclass Solution {\n\n\t\t\tpublic int minSubarray(int[] nums, int p) {\n\n\t\t\t\tlong sum = 0;\n\t\t\t\tfor (int n : nums) sum += n;\n\t\t\t\tif (sum < p) return -1;\n\n\t\t\t\tint R = (int)(sum % p);\n\t\t\t\tif (R == 0) return 0;\n\n\t\t\t\tMap<Integer, Integer> map = new HashMap<>();\n\t\t\t\tint min = Integer.MAX_VALUE;\n\t\t\t\tsum = 0;\n\n\t\t\t\tmap.put(0, -1);\n\t\t\t\tfor (int i = 0; i < nums.length; i++) {\n\n\t\t\t\t\tsum += nums[i];\n\t\t\t\t\tint r = (int)(sum % p);\n\n\t\t\t\t\tint target = r - R;\n\t\t\t\t\tif (target < 0) target += p;\n\n\t\t\t\t\tif (map.containsKey(target)) {\n\t\t\t\t\t\tmin = Math.min(min, i - map.get(target));\n\t\t\t\t\t}\n\n\t\t\t\t\tmap.put(r, i);\n\t\t\t\t}\n\n\t\t\t\tif (min == nums.length || min == Integer.MAX_VALUE) return -1;\n\t\t\t\treturn min;\n\t\t\t}\n\t\t}
[]