✅Easy C++ Solution | Intuition & Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nLooking at the constraints, we can conclude that if we generate all subarrays in O(n^3)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLooking at the constraints, we can conclude that if we generate all subarrays in O(n^3), it will be accepeted.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nGenerate all subarrays, while pushing elements in the subarray which we are generating we will check if it is divisible by p or not and maintain a count variable. If count <= k then we will store it in a set, since we need different subarrays.\n \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^3)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n```\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        set<vector<int>>s;\n        for(int i = 0; i < nums.size(); i++){\n            for(int j = i; j < nums.size(); j++){\n                vector<int> arr;\n                int count = 0;\n                for(int l = i; l <= j; l++){\n                    arr.push_back(nums[l]);\n                    if(nums[l]%p == 0){\n                        count++;\n                    }\n                }\n                if(count <= k){\n                    s.insert(arr);\n                }\n            }\n        }\n        return s.size();\n    }\n};\n```\n\nWe can do small optimisation, it is not required to build subarray from the start we can also keep track of it in two loops only. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2 log n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n\n# Code\n\n```\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        set<vector<int>>s;\n        for(int i = 0; i < nums.size(); i++){\n            vector<int> arr;\n            int count = 0;\n            for(int j = i; j >= 0; j--){\n                arr.push_back(nums[j]);\n                if(nums[j]%p == 0){\n                    count++;\n                }\n                if(count <= k){\n                    s.insert(arr);\n                }else{\n                    break;\n                }\n            }\n        }\n        return s.size();\n    }\n};\n```\n
['Ordered Set', 'C++']