✅[C++] Intuitive Trie Approach w/Explanation
This question is a little tricky. At first, i thought it could be done with two pointers, just like its base questions, but \nthen i realised that we have to sk
This question is a little tricky. At first, i thought it could be done with two pointers, just like its base questions, but \nthen i realised that we have to skip the repeated occurrances of subarrays. Thats where that method fails. That method counts the repeated subarrays as well, but this question has asked us to skip them.\n\nNow, since we are asked to skip the repeated subarrays, we can also use set to store all the subarrays generated(since constraints are small) but that would be space consuming. \n**Therefore, best way to solve such problems is Trie**\n\n#### How do we solve with Trie?\nI assume that you alread know about Trie Data structure and its functioning. In case you dont, you can learn it from [TechDose](https://www.youtube.com/watch?v=6PX6wqDQE20&list=PLEJXowNB4kPyi859E6qGUs7jlpQehJndl) who has explained it in the best way possible. \n\n\n\nNow, we will maintain a Trie of subsets of the array. We will iterate the array in O(n<sup>2</sup>) and in each iteration, we will count the valid subarrays starting from nums[i]. If at any point, the count(that stores the count of numbers divisible by p in that subarray) is greater than k, we break the loop for that i. \nWe check if this subset is already present in our Trie or not. If it is present, we just skip it, else, we add the current element to trie, update the subset and update our ans variable. \nFor ex.\n```\n[8,8,8]\n3\n17\nPossible subsets are [8], [8,8], [8,8,8]. Lets do a dry run. \ni=0, j=0, 8 will be inserted and ans = 1\ni=0, j=1, another 8 will be inserted and ans = 2\ni=0, j=2, another 8 will be inserted and ans = 3\n\ni=1,j=1, this time, 8 will not be inserted because temp->next[8] already exists\ni=1,j=2, this time also, 8 wont be inserted because temp->next[8] exists already\n\ni=2,j=2, this time too, nothing happens.\nThus \'ans = 3\'\n```\n\n```\nclass Trie {\npublic:\n    int val;\n    unordered_map <int,Trie*> next;\n};\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        int ans = 0;\n        Trie* root = new Trie();\n        for(int i = 0; i<nums.size(); i++){\n            Trie* temp = root;\n            int count = 0;\n            for(int j = i; j<nums.size(); j++){\n                if(nums[j]%p==0) count++;\n                if(count>k) break;\n                \n                if(!temp->next[nums[j]]){\n                    temp->next[nums[j]] = new Trie();\n                    ans++;\n                }\n                temp = temp->next[nums[j]];\n            }\n        }\n        return ans;\n    }\n};\n```
['Trie', 'C', 'C++']