LeetCode 2261. K Divisible Elements Subarrays

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Trie {
    unordered_map<int, Trie*> ch;
    int cnt = 0;
    int insert(vector<int>& nums, int i, int k, int p) {
        if (i == nums.size() || k - (nums[i] % p == 0) < 0)
            return 0;
        if (ch[nums[i]] == nullptr)
            ch[nums[i]] = new Trie();
        return (++ch[nums[i]]->cnt == 1) +
            ch[nums[i]]->insert(nums, i + 1, k - (nums[i] % p == 0), p);
    }
};
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        int ans = 0;
        Trie t;
        for (int i = 0; i < nums.size(); ++i)
            ans += t.insert(nums, i, k, p);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        unordered_set<string> s;
        for(int i = 0; i < nums.size(); i++) { // start point.
            int cnt = 0;
            string tmp = "";
            for (int j = i; j < nums.size(); j++) { // end point.
                if (nums[j] % p == 0 && ++cnt > k) break;
                tmp += nums[j] + '0';
                s.insert(tmp);
            }
        }
        return s.size();
    }
};