Java Trie O(n) clean solution beats 86% at the moment
Approach\n\nWe keep a count of numbers that are divisible by p. If count is less than k we iterate the trie. If the the trie node is not visited we increase res
# Approach\n\nWe keep a count of numbers that are divisible by p. If count is less than k we iterate the trie. If the the trie node is not visited we increase result. One thing to make sure is to iterate from the back side of subarray. This will give us only the new additions. Example if we have a trie branch 1,2,3,4 and the next valid integer is 5. The new subarray formed are [5], [5,4], [5,4,3], [5,4,3,2], [5,4,3,2,1].\nSo count increase by 5.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\n\n    class Node{\n\n        boolean found;\n        Node[] ch;\n        public Node(){\n            this.found = false;\n            this.ch = new Node[201];\n        }\n    }\n\n    Node curr = new Node();\n    int res=0;\n\n    void build(int[] nums, int a, int b){\n\n        //Building the Trie and increasing the count (res) if\n        //the node is visited for the first time \n        Node root = curr;\n        for(int i=b;i>=a;i--){\n\n            if(root.ch[nums[i]]==null){\n                root.ch[nums[i]] = new Node();\n                res++;\n            }\n            root = root.ch[nums[i]];\n        }\n        \n    }\n    \n    public int countDistinct(int[] nums, int k, int p) {\n        \n        //Queue<Integer> que = new LinkedList<>();\n        int n = nums.length;\n        int start =0;\n        int count=0;\n        \n        for(int i=0;i<n;i++){\n\n            if(nums[i]%p==0)count++;\n\n            while(count>k){\n                if(nums[start++]%p==0)count--;\n            }\n            // Can also use a queue to find the index\n            // of last occurence of an element divisible by p\n            //if(que.size()>k)start = que.poll()+1;\n            build(nums, start, i); \n        }\n        return res;\n\n    }\n}
['Trie', 'Queue', 'Java']