This article is participating in Python Theme Month. See the link for details

Topic describes

This is 1711 on LeetCode. Feast count, medium difficulty.

Tag: hash table, bit operation

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. The result is mod 10910^9109 + 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.Copy the code

Example 2:

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

Tip:

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

Enumerate the previous number (TLE)

Is a simple idea, all the number in the traversal deliciousnessdeliciousnessdeliciousness back once upon a time, when the traverse to subscript iii, Check back to see if numbers subscript less than iii can be added to deliciousness to form a power of 222.

So this is O(n2)O(n^2)O(n2), so to prevent the same number from being counted twice, we can use a hash table to keep track of how many times a certain number occurs, but that doesn’t change the algorithm is still O(n2)O(n^2)O(n2).

And we need a check method to determine if something is a power of 222:

  • The naive approach is to apply trial division to XXX, of course, because of the accuracy problem, we need to use multiplication to achieve trial division;
  • Another good practice is to use bitwise operations to find the nearest power of 222 that matches “greater than or equal to XXX” and determine if it is the same as XXX.

How different are the two approaches? Methods a complexity to O (log ⁡ n) O (\ log {n}) O (logn), method 2. O (1) O (1) O (1).

According to the data range 0<=deliciousness[I]<=2200 <=deliciousness[I]<=2 ^{20}0<=deliciousness[I]<=220, method one is to execute no more than 222222 cycles.

Obviously, it is not the key to judge the power of 222, and the OJ judgment is only stuck on TLE of 60/7060/7060/70 and 62/7062/7062/70 respectively.

But through such analysis, we can find that the practice of “enumerating the previous number” is with
n n Related, while enumeration “may occur
2 2 The “power of” has definite scope, which leads us to solution two.

Java code:

class Solution {
    int mod = (int)1e9+7;
    public int countPairs(int[] ds) {
        int n = ds.length;
        long ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = ds[i];
            for (int other : map.keySet()) {
                if (check(other + x)) ans += map.get(other);
            }
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        return (int)(ans % mod);
    }
    boolean check(long x) {
        / / method
        // long cur = 1;
        // while (cur < x) {
        // cur = cur * 2;
        // }
        // return cur == x;
        
        / / method 2
        return getVal(x) == x;
    }
    long getVal(long x) {
        long n = x - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n < 0 ? 1 : n + 1; }}Copy the code

Python3 code:

class Solution:
    mod = 10支那9 + 7
    def countPairs(self, deliciousness: List[int]) - >int:
        n = len(deliciousness)
        ans = 0
        hashmap = Counter()
        for i in range(n):
            x = deliciousness[i]
            for other in hashmap:
                if self.check(other+x):
                    ans += hashmap[other]
            hashmap[x] += 1
        return ans % self.mod
    
    def check(self, x) :
        "" # cur = 1 while cur *= 2 return cur == x ""
        
        Method # 2
        return self.getVal(x) == x
    
    def getVal(self, x) :
        n = x - 1
        # Java >>> : Unsigned right shift. Both positive and negative values complement 0. Python does not need to
        n |= n >> 1
        n |= n >> 2
        n |= n >> 4
        n |= n >> 8
        n |= n >> 16
        return 1 if n < 0 else n + 1
Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

Powers of enumeration 2 (inclusive exclusion principle)

According to the analysis of simple solution, we can use “hash” first of all the deliciousnessdeliciousnessdeliciousness show the number of statistics.

Then, for each number XXX, check all possible powers iii of 222, and check t= I −xt = i-xt = I −x from the “hash table” for the presence of t= I −xt = I −x, and implement the count.

Some details: If t= I − Xt = I-Xt = I − X exists in the hash table, and T =xt =xt = X, the number of options should be (CNTS [x]−1 ∗ CNTS [x](CNTS [x] -1) * CNTS [x](CNTS [x]−1)∗ CNTS [X]; The other general cases are CNTS [T]∗ CNTS [x] CNTS [T] * CNTS [x] CNTS [T]∗ CNTS [X].

At the same time, in this counting way, we will count the binary group (x,t)(x, t) twice respectively (traversing XXX and traversing TTT), so finally, we need to use the inclusive exclusion principle to halve the operation of repeated counting.

Java code:

class Solution {
    int mod = (int)1e9+7;
    int max = 1 << 22;
    public int countPairs(int[] ds) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int d : ds) map.put(d, map.getOrDefault(d, 0) + 1);
        long ans = 0;
        for (int x : map.keySet()) {
            for (int i = 1; i < max; i <<= 1) {
                int t = i - x;
                if (map.containsKey(t)) {
                    if (t == x) ans += (map.get(x) - 1) * 1L * map.get(x);
                    else ans += map.get(x) * 1L * map.get(t);
                }
            }
        }
        ans >>= 1;
        return (int)(ans % mod); }}Copy the code

Python3 code:

class Solution:
    mod = 10支那9 + 7
    maximum = 1 << 22
    def countPairs(self, deliciousness: List[int]) - >int:
        hashmap = Counter(deliciousness)
        ans = 0
        for x in hashmap:
            i = 1
            while i < self.maximum:
                t = i - x
                if t in hashmap:
                    if t == x:
                        ans += (hashmap[x] - 1) * hashmap[x]
                    else:
                        ans += hashmap[x] * hashmap[t]
                i <<= 1
        ans >>= 1
        return ans % self.mod
Copy the code
  • Time complexity: Set CCC to 2212^{21}221 based on the data range. O(n∗log⁡C)O(n * \log{C})O(n∗logC)
  • Space complexity: O(n)O(n)O(n)

Powers of enumeration 2 (side traversal side count)

Of course, we can also take the “count as you go” approach, so that the mod can be done in the traversal logic, which incidentally does not count with longlonglong (and does not use % for mod).

Java code:

class Solution {
    int mod = (int)1e9+7;
    int max = 1 << 22;
    public int countPairs(int[] ds) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (int x : ds) {
            for (int i = 1; i < max; i <<= 1) {
                int t = i - x;
                if (map.containsKey(t)) {
                    ans += map.get(t);
                    if (ans >= mod) ans -= mod;
                }
            }
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        returnans; }}Copy the code

Python3 code:

class Solution:
    mod = 10支那9 + 7
    maximum = 1 << 22
    def countPairs(self, deliciousness: List[int]) - >int:
        hashmap = defaultdict(int)
        ans = 0
        for x in deliciousness:
            i = 1
            while i < self.maximum:
                t = i - x
                if t in hashmap:
                    ans += hashmap[t]
                    if ans >= self.mod:
                        ans -= self.mod
                i <<= 1
            hashmap[x] += 1
        return ans
Copy the code
  • Time complexity: Set CCC to 2212^{21}221 based on the data range. O(n∗log⁡C)O(n * \log{C})O(n∗logC)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.1711 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.