“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

A big meal is a meal that contains exactly two different dishes, the sum of which equals a power of two.

You can make a big meal with any two dishes.

Given an integer array deliciousness, where deliciousness[I] is the iciousness of the ith dish, returns the number of different dishes you can make from the array. I have to mod 109 plus 7.

Note that as long as the subscripts are different, they can be considered different, even if they are equally delicious.

Example 1:

The degree of delicious food can be divided into (1,3), (1,7), (3,5) and (7,9). They add up to 4, 8, 8 and 16, all powers of 2.

Example 2:

The degree of delicious food can be divided into 3 kinds (1,1), 9 kinds (1,3), and 3 kinds (1,7).

Thought analysis

From the amount of data, it can be inferred that the complexity should be roughly n(logn). In order to reduce the time cost, only binary search is more suitable for this problem. 1. Find the NTH power 2 of all 2’s that are larger than the current number but less than twice the maximum number in the array. Subtract the NTH power of 2 from the current number, and use binary search to find the left and right boundaries of the number in the array. The right boundary-left boundary +1 will get the number of times, and so on.

Solution 1: Map
var countPairs = function (deliciousness) {
  const mod = 10 ** 9 + 7
  const map = new Map(a)for (const num of deliciousness) {
    if(! map.has(num)) map.set(num,0)
    map.set(num, map.get(num) + 1)}let ans = 0
  const visited = new Set(a)for (const [num, count] of map) {
    let flag = false
    for (let i = 0; i <= 21; i++) {
      const sum = 2 ** i
      if(! visited.has(sum - num) && map.has(sum - num)) {if (sum - num === num) {
          ans = (ans + (count * (count - 1)) / 2) % mod
        } else {
          ans = (ans + count * map.get(sum - num)) % mod
        }
        flag = true}}if (flag) visited.add(num)
  }
  return ans
}
Copy the code
Solution 2: Map+ bit operation

X * 2^y = 1; x * 2^y = 1;

class Solution {
public:
    typedef long long LL;
    int mod = 1e9 + 7;
    int countPairs(vector<int>& deliciousness) {
        unordered_map<int.int> cnt;
        for(auto & x : deliciousness) ++cnt[x];
        int ans = 0;
        LL a = 0, b = 0;
        for(auto & [k, c] : cnt){
            for(int i = 0; i <= 21; i++){
                int target = (1 << i) - k;
                if(cnt.count(target)){
                    if(target == k) a += c * (c - 1LL) / 2;
                    else b += (LL)c * cnt[target];
                    }
                }
            }
        ans = (a + b / 2) % mod;
        returnans; }};Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤