LeetCode 1711. Count Good Meals

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int MOD = 1'000'000'007;
class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int, int> freq;
        int maxSum = 0;
        int ans = 0;
        for (int d : deliciousness) {
            maxSum = max(maxSum, d * 2);
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                int t = sum - d;
                int c = freq.find(t) != freq.end() ? freq[t] : 0;
                ans = (ans + c) % MOD;
            }
            ++freq[d];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MOD = 1000000007;
int freq[(1 << 21) + 1] = {0,}, maxSum, ans;
class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        memset(freq, 0, sizeof freq);
        maxSum = ans = 0;
        for (int &d : deliciousness)
            ++freq[d];
        for (int &d : deliciousness) {
            --freq[d];
            for (int sum = 1; sum <= (1 << 21); sum <<= 1) {
                int t = sum - d;
                if (t >= 0)
                    ans = (ans + freq[t]) % MOD;
            }
        }
        return ans;
    }
};