Count Good Meals – LeetCode

This is the fifth question of our AlgoMaster Sheet from Hashing Section. Hope you are enjoying our series now, if you have any suggestions make sure to drop your comments down as well – we will try to improve our content as per suggestions. Similarly, we hope that you try the question for at least an hour, before moving to the solution. With that being said let’s dive deep into today’s question!!

Problem Statement

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i​​​​​​th​​​​​​​​ item of food, return the number of different good meals you can make from this list modulo 109 + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:

• 1 <= deliciousness.length <= 105
• 0 <= deliciousness[i] <= 220

Intuition:

This problem is pretty straightforward as compared to the previous ones we have solved- given a deliciouness[] array we have to find all those pairs whose sum is a Power Of Two. In other words, we need to find all those pairs (a, b) such that (a + b = 2 ^ n) where n can be anything from (0 to 21). How we came to that by looking into the constraints- 0 <= deliciouness[i] <= 2 ^ 20.

Looking into the question, we can safely say that (0, 1) is a valid pair because 2 ^ 0 = 1. Similarly, (2 ^ 20, 2 ^ 20) is also a valid pair, if we sum them up we can find that the max power for which we need to check for 2 is 21. Now with that being said let’s address the elephant in the room – the MODULUS operation. MOD operations are very common in DSA and we hope you have come across it in some question or something. If not, you need not worry, we will try to explain how MOD is used in this question and how we can use it to solve the question at hand.

MOD value is 1000000007. The need for such a big value is that the Number of Possible Pairs will be very very large and such an addition will lead to INTEGER OVERFLOW, that’s why we need to take the MOD Value into our Hashing array. Now with everything said, we can safely discuss our approach now.

We will iterate over the array of deliciousness[] and for every value deliciousness[i] we will use a FOR LOOP from 0 to 21 [both inclusive] and we will check if we have encountered any other such value like whose sum will add up to become a power of two. At the end of the for loop, we will store the count of the frequency of deliciousness[i] in our HashMap.

Lastly, our HashMap will store the Frequency of a number occurring inside the deliciousness[] array- this is because, for any value of (a, b)- for any fixed value of a, we can make the number of pairs equal to the number of occurrence of b in the array, provided (a + b = 2 ^ n) which is what we need to check every time.

Algorithm:-

1. Declare a hashMap to store the elements of deliciousness[] and their frequency
2. For every value in deliciousness[], we run a for loop for j = 0 till j <= 21 and check for every possible power of 2
3. As we are looking for pair (a,b), [a, in this case, is equal to deliciousness[i] ], we check if we have encountered b before or not.
4. If we have visited b before, then we update our ans by the frequency of b, which is the map[key] in C++
5. Also, as the number of pairs might be more than INT_MAX, we need to take MOD with 1000000007.
6. In the end, we return the number of such pairs we have visited.

Code:-

class Solution {
public:
     int countPairs(vector<int>& deliciousness) 
     {
        long long int MOD = 1e9 + 7 ;  // Store the value of MOD in variable
        
        int n = deliciousness.size() ;

        unordered_map<int , int> map ; // Map to store the previous integer with its frequency
        
        long long int  ans = 0 ; // To avoid confusion, we are taking ans as Long Long Int 

        for(int i = 0 ; i < n ; i++)
        {
            int val = deliciousness[i] ; // Current Deliciousness
            
            long long int power = 1 ;

            // This loop will run from j = 0 till 21 and check for all possible powers of two

            for(int j = 0 ; j <= 21 ; j++)  
            {
                int key = power - val ; // Key will be equal to the (power - val)

                // If we have encountered the key before, we need to update our ans 

                if(map.find(key) != map.end() )
                {
                    int currCount = map[key]  ; // We store the number of possible pairs from our hashMap 

                    ans += (currCount % MOD) ; // We take the MOD and update our ans by that Modulated value 
                }
                
                power *= 2 ;  // After every iteration, we update our power as power * 2
            }
            
            // At the end, we store the frequency of Current Deliciousness into our HashMap
            
            map[val] += 1 ;
        }
        
        // Before returning, we take the Modulus with ans and Explicitly Type Cast as Integer
        
        return (int) (ans % MOD) ;  
    }

};

class Solution 
{
    public int countPairs(int[] deliciousness) 
    {
        int MOD = 1000000007;  //Store the value of MOD in variable
        int n = deliciousness.length;
        HashMap<Integer,Integer> map = new HashMap<>(); //Map to store the previous integer with its frequency
        
        long ans = 0L;
        for(int i=0; i<n; i++)
        {
            int val = deliciousness[i];
            int power = 1;
            for(int j=0; j<=21; j++)   //According to constraints the range is 0 to 2^20
            {
                if(map.containsKey(power - val))
                    ans = ans + map.get(power - val);  //Storing the frequency in answer if its valid combination
                
                power = power * 2;  //Incrementing the power
            }
            
            // Storing the frequency of each integer in the map
            if(map.containsKey(val))
                map.put( val, map.get(val) + 1);
            else
                map.put(val,1);
        }
        return (int) (ans % MOD); //Before returning we are taking the modulus of the ans in long
    }
}

Analysis of Time & Space Complexity:-

In this problem, we are traversing the deliciousness[] array once for every element inside the array[], and we are running a for loop 22 times[constant and independent of N]. Thus our Time Complexity boils down to O(N * 22), which roughly boils down to O(N). Similarly, we are using an external HashMap to store the frequency of the elements inside deliciousness[], so our Space Complexity is O(N).

If you still have any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn, Tanmay Dutta: LinkedIn, Raj Chowdhury: LinkedIn & Arjan Hazra: LinkedIn