Description

Submission

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        const int M = 1e9 + 7;
        map<int, int> nums;

        for(auto x: deliciousness) {
            ++nums[x];
        }

        int maximum = nums.rbegin()->first;

        vector<int> powOfTwo;

        for(int i = 0; i <= 21; ++i) {
            int val = (1 << i);
            if(val > maximum * 2) break;
            powOfTwo.push_back(val);
        }

        long long ret = 0;

        for(auto it = nums.begin(); it != nums.end(); ++it) {
            for(auto x: powOfTwo) {
                auto t = x - it->first;
                auto it2 = nums.lower_bound(t);
                if(it2->first < it->first) continue;
                if(it2 != nums.end() && it2->first == t) {
                    if(t == it->first) {
                        if(it->second != 1) {
                            ret += (long long)it->second * (it->second-1) / 2;     // combination
                        } 
                    }
                    else ret += (long long)it->second * it2->second % M;
                }
                ret %= M;
            }
        }

        return ret;
    }
};