C# Brute-Force with array keys - Straightforward
Intuition\n Describe your first thoughts on how to solve this problem. \nFrom studying the given examples, and reading the problem carefully, here is what the p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFrom studying the given examples, and reading the problem carefully, here is what the problem wants us to do:\n\nCount all unique subarrays of nums where the count of numbers evenly divisible by p in the subarray is no greater than k.\n\nThe keyword here is unique. For example:\n\nif nums = [2, 2, 2], p = 5, and k = 3, the answer would be 3.\n\nEven though, for example, there are 2 subarrays of [2, 2], we only count the first [2, 2] that appears, and none after. The same goes for the 3 subarrays of [2], we only count the first [2].\n\nWhat is a data structure that only stores 1 instance of each element, and can quickly determine whether we\'ve seen that element before or not? A HashSet!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Instantiate a HashSet of strings - seenArr.\n\n2. Initialize two integers - len = nums.Length and total (to count new sub arrays) = 0.\n\n3. Instantiate a StringBuilder - sb - it will be used to build the array-keys that we will run against seenArr to determine if we\'ve seen an array before.\n\n4. Run a for-loop, starting at 0 and ending when i = len. Inside of this loop, initialize two integers - currP = 0 and ind = i. Also use sb.Clear() at the start to clear the StringBuilder without having to use memory by creating a new one. \n\ncurrP will be our count of elements in the sub array that are divisble by p, ind will be how we extend the range of our sub array.\n\n5. Inside the for-loop, run a while-loop while ind is less than len, and in that while-loop:\n\nFirst check to see if nums[ind] is divisible by p. If it is, check to see if your currP is equal to k. If currP == k, break from the loop. Otherwise if currP != k, increment currP by 1.\n\nIf the previous section didn\'t cause a break in the loop, then we can continue and append nums[ind] and a de-limiting character, \'-\', to sb.\nConvert sb to a string with the .ToString() method and check if that string is contained in seenArr.\n\nIf it is not in seenArr, add it to seenArr and increment total by 1.\n\nFinally at the end increment ind by 1.\n\n6. Return total.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n * n)$$\n\nThe worst-case time complexity would be if every single ind can travel from the starting point all the way to len. This is tantamount to n squared run-time.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n * n)$$\n\nFor every valid index we create 1 key from StringBuilder. Because the above could run n * n times, that means we may have to create n * n strings/keys.\n\n# Code\n```\npublic class Solution {\n    public int CountDistinct(int[] nums, int k, int p) {\n        HashSet<string> seenArr = new();\n        // Each subarray will have a key - Only count new subarrays\n        // if they aren\'t in seenArr.\n\n        int len = nums.Length;\n        int total = 0;\n\n        StringBuilder sb = new(); // For building arr-keys\n\n        for (int i = 0; i < len; i++){\n            sb.Clear();\n            int currP = 0;\n            int ind = i;\n            while (ind < len){\n                if (nums[ind] % p == 0){\n                    if (currP == k) break;\n                    currP++;\n                }\n                sb.Append(nums[ind]).Append(\'-\');\n                var key = sb.ToString();\n                if (!seenArr.Contains(key)){\n                    seenArr.Add(key);\n                    total++;\n                }\n                ind++;\n            }\n        }\n\n        return total;\n    }\n}\n```
['C#']