Simple prefix sum: O(n^2). 84% fast and 87% memory efficient. Enjoy!!
This problem can be easily done with calculating prefix sum of numbers which are divisible by p.\n- In this approach, the subarrays are kept as strings, as we d
This problem can be easily done with calculating prefix sum of numbers which are divisible by p.\n- In this approach, the subarrays are kept as strings, as we do not want the actual subarrays, rather only the count.\n```\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        int n = nums.size();\n        unordered_set<string> set;\n        \n        vector<int> prefSum(n + 1);\n        for(int i = 0; i < n; i++)\n            prefSum[i + 1] = prefSum[i] + (nums[i] % p == 0);\n        \n        for(int i = 0; i < n; i++){\n            string subAr = "";\n            for(int j = i; j < n; j++){\n                if(prefSum[j + 1] - prefSum[i] <= k){\n                    subAr.push_back(nums[j]);\n                    set.insert(subAr);\n                }\n                else break;\n            }\n        }\n        \n        return set.size();\n    }\n};\n```\n**Upvote ^** if you like.
['C', 'Prefix Sum', 'C++']