1711. Count Good Meals

문제: https://leetcode.com/problems/count-good-meals/

Count Good Meals - LeetCode

 deliciousness의 값 중 두 개를 더했을 때 2의 n승의 값이 되는지 판별하는 문제다.

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        int mod = 1000000000 + 7;
        
        vector<int> twosPower;
        int v = 1;
        
        for(int i = 0; i < 22; i++){
            twosPower.push_back(v);
            v *= 2;
        }
        
        int n = deliciousness.size();
        
        unordered_map<int, int> lookup;
        long long ans = 0;
        
        for(int i = 0; i < n; i++){
            int t = deliciousness[i];
            for(auto twos : twosPower){
                int target = twos - t;
                if(target < 0) continue;
                if(lookup.find(target) != lookup.end()){
                    ans += lookup[target];
                }
            }
            lookup[t]++;
        }
        return ans % mod;
    }
};

 two sum처럼 이전값들을 다 unordered_map에 넣어두고 조건에 맞으면 해당 카운트를 ans에 더한다.  

 

Time complexity: O(n)

Space complexity: O(n) - lookup