C# Solution for Make Sum Divisible By P Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key observation is that if the sum of the entire array isn\u2019t divisible by p, w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key observation is that if the sum of the entire array isn\u2019t divisible by p, we need to remove a subarray such that the sum of the remaining elements becomes divisible by p. To achieve this, we look for a subarray whose sum (mod p) equals the \u201Cremainder\u201D of the total sum (mod p). Removing such a subarray will make the sum of the rest of the elements divisible by p.\n\nWe can efficiently track prefix sums modulo p and use this information to detect subarrays that, when removed, lead to a sum divisible by p.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tTotal Sum and Remainder: Calculate the total sum of the array and its remainder when divided by p. If the total sum is already divisible by p, no removal is needed, and we return 0.\n2.\tPrefix Sums and Hash Map: We iterate through the array while keeping track of the current prefix sum modulo p. We store the modulo values in a dictionary (prefixMap) with their indices. The dictionary helps us quickly determine if there is a previously encountered prefix sum that forms a valid subarray that, when removed, results in the sum being divisible by p.\n3.\tModulo Arithmetic: For each prefix sum at index i, we calculate the required targetMod (the remainder we need to remove). If targetMod has been seen before (stored in the dictionary), we can calculate the length of the subarray to remove. We keep track of the minimum length.\n4.\tResult: If no valid subarray is found, we return -1. Otherwise, return the minimum length of the subarray.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n): The algorithm involves iterating through the array once, performing constant-time operations for each element (hash map lookups and insertions). Therefore, the overall time complexity is linear with respect to the number of elements in the array.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n): The space complexity is due to the hash map (prefixMap), which can potentially store n entries (one for each element in the array). Thus, the space complexity is linear.\n\n# Code\n```csharp []\npublic class Solution {\n    public int MinSubarray(int[] nums, int p) {\n        int n = nums.Length;\n        long totalSum = 0;\n        \n        foreach (int num in nums) {\n            totalSum += num;\n        }\n\n        long remainder = totalSum % p;\n        if (remainder == 0) {\n            return 0;\n        }\n\n        Dictionary<long, int> prefixMap = new Dictionary<long, int>();\n        prefixMap[0] = -1;  \n\n        long prefixSum = 0;\n        int minLength = n;\n\n        for (int i = 0; i < n; i++) {\n\n            prefixSum += nums[i];\n\n            long currentMod = prefixSum % p;\n\n\n            long targetMod = (currentMod - remainder + p) % p;\n\n\n            if (prefixMap.ContainsKey(targetMod)) {\n                minLength = Math.Min(minLength, i - prefixMap[targetMod]);\n            }\n\n            prefixMap[currentMod] = i;\n        }\n\n        return minLength == n ? -1 : minLength;\n    }\n}\n```
['C#']