Leetcode Problem 1711. Count Good Meals

1711. Count Good Meals

Leetcode Solutions

Hash Table and Power of Two Search

  1. Initialize a hash table (dictionary) to store the frequency of each deliciousness value.
  2. Initialize a variable result to store the number of good meals.
  3. Iterate over each value in the deliciousness array. a. For each value, iterate through all powers of two up to 2^21 (since the maximum value of deliciousness is 2^20). b. Calculate the complement by subtracting the current value from the current power of two. c. If the complement exists in the hash table, add its frequency to result. d. If the current value is the same as the complement, subtract one from the frequency before adding to result to avoid double-counting.
  4. After processing all values, divide result by 2 to correct for double-counting pairs.
  5. Return result modulo 10^9 + 7.
UML Thumbnail

Brute Force with Early Stopping

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...