Count Good Meals

Medium
1141.

Count Good Meals

Count Good Meals is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.

deliciousness[i] is how tasty the i-th dish on the menu is. A good meal is a pair of two different dishes (different indices) whose deliciousness adds up to a power of two (1, 2, 4, 8, ...).

Return the number of good meals, i.e. pairs of indices i < j with deliciousness[i] + deliciousness[j] a power of two. Dishes with equal deliciousness but different indices are different dishes.

Return the count modulo 10^9 + 7.

Example 1

Input
deliciousness = [2,6,1,1]
Output
2
Explanation
`2 + 6 = 8` and `1 + 1 = 2`.

Example 2

Input
deliciousness = [0,1,0]
Output
2
Explanation
Each 0 pairs with the 1 to make `1 = 2^0`; `0 + 0` is not a power of two.

Example 3

Input
deliciousness = [4,4,12,4]
Output
6
Explanation
Three pairs of 4s make 8, and each 4 with 12 makes 16.

Constraints

  • 1 <= deliciousness.length <= 10^5
  • 0 <= deliciousness[i] <= 2^20
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} deliciousness
 * @return {number}
 */
var countPairs = function(deliciousness) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Good Meals — Solution in Python, Java & C++

Count Good Meals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Good Meals is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

deliciousness[i] is how tasty the i-th dish on the menu is. A good meal is a pair of two different dishes (different indices) whose deliciousness adds up to a power of two (1, 2, 4, 8, ...).

Return the number of good meals, i.e. pairs of indices i < j with deliciousness[i] + deliciousness[j] a power of two. Dishes with equal deliciousness but different indices are different dishes.

Return the count modulo 10^9 + 7.

Example 1

Input: deliciousness = [2,6,1,1]
Output: 2
Explanation: `2 + 6 = 8` and `1 + 1 = 2`.

Example 2

Input: deliciousness = [0,1,0]
Output: 2
Explanation: Each 0 pairs with the 1 to make `1 = 2^0`; `0 + 0` is not a power of two.

Example 3

Input: deliciousness = [4,4,12,4]
Output: 6
Explanation: Three pairs of 4s make 8, and each 4 with 12 makes 16.

Constraints

  • 1 <= deliciousness.length <= 10^5
  • 0 <= deliciousness[i] <= 2^20

Hints for Count Good Meals

  1. Hint 1

    A pair sum is at most 2^21, so there are only 22 powers of two it could equal.

  2. Hint 2

    For each dish, the partner it needs for power 2^p is exactly 2^p - deliciousness[i].

  3. Hint 3

    Scan left to right with a hash map of counts seen so far; for each dish add the counts of all 22 possible partners, then record the dish.

How to solve Count Good Meals

Instead of checking every pair, check every power of two: for each dish there are only 22 possible target sums, and each fixes the partner's value.

Approach

  1. Keep count[value] for dishes already scanned.
  2. For dish x, for p from 0 to 21, add count[2^p - x] to the answer.
  3. Then increment count[x].
  4. Reduce the answer modulo 10^9 + 7.

Why it works

Each good pair i < j is counted exactly once — at j, under the unique power equal to their sum, when dish i is already in the table. Sums never exceed 2^21, so no power is missed.

Complexity

  • Time — O(22 · n)
  • Space — O(n)

Pitfalls

  • Zero is allowed: 0 + 1 = 1 = 2^0 is a good meal, but 0 + 0 = 0 is not a power of two.
  • Go up to 2^21 — two dishes of 2^20 sum to 2^21.
  • Count only earlier dishes so a dish never pairs with itself and no pair is counted twice.

Reference solution

Python

from typing import List

def countPairs(deliciousness: List[int]) -> int:
    MOD = 10 ** 9 + 7
    count = {}
    ans = 0
    for x in deliciousness:
        for p in range(22):
            ans += count.get((1 << p) - x, 0)
        count[x] = count.get(x, 0) + 1
    return ans % MOD

Java

public static int countPairs(int[] deliciousness) {
    final int MOD = 1000000007;
    Map<Integer, Integer> count = new HashMap<>();
    int ans = 0;
    for (int x : deliciousness) {
        for (int p = 0; p <= 21; p++) {
            Integer c = count.get((1 << p) - x);
            if (c != null) ans = (ans + c) % MOD;
        }
        count.merge(x, 1, Integer::sum);
    }
    return ans;
}

C++

int countPairs(vector<int>& deliciousness) {
    const int MOD = 1000000007;
    unordered_map<int, int> count;
    int ans = 0;
    for (int x : deliciousness) {
        for (int p = 0; p <= 21; p++) {
            auto it = count.find((1 << p) - x);
            if (it != count.end()) ans = (ans + it->second) % MOD;
        }
        count[x]++;
    }
    return ans;
}

JavaScript

var countPairs = function(deliciousness) {
    var MOD = 1000000007;
    var count = new Map();
    var ans = 0;
    for (var i = 0; i < deliciousness.length; i++) {
        var x = deliciousness[i];
        for (var p = 0; p <= 21; p++) {
            var c = count.get((1 << p) - x);
            if (c !== undefined) ans = (ans + c) % MOD;
        }
        count.set(x, (count.get(x) || 0) + 1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets