Count good meals

Array Hash Table

32.6% acceptance

Feb 25, 2026

1126

246

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 ith 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn count_pairs(deliciousness: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let mut cnt: HashMap<i32, i64> = HashMap::new();
    let mut ans: i64 = 0;
    for &d in &deliciousness {
      for k in 0..=21 {
        let target = (1i32 << k) - d;
        if target >= 0 {
          ans = (ans + cnt.get(&target).copied().unwrap_or(0)) % MOD;
        }
      }
      *cnt.entry(d).or_insert(0) += 1;
    }
    ans as i32
  }
}