XOR Pairs

Interview

Time limit1sMemory limit1024 MB

Summary

Count ordered pairs (A, B) where A and B are at most A XOR B, A XOR B is at most N, and A XOR B is not in the set S.

Level: Medium5 of 10
Topics: Bit manipulation, Math, Hash map
Solved: No attempts yet

Problem

XOR is a bitwise operator that outputs 1 if and only if the corresponding input bits differ (one of them is 1 while the other is 0). The XOR operator is usually written with the symbol $\oplus$ , or with the character ^ (caret) in most programming languages. For example, $(10 \oplus 6) = 12$ .

10 =>  1010
 6 =>  0110
      ----- ⊕
       1100   => 12

In this problem, you are given an integer $N$ and a set of integers $S_1, \ldots, S_M$ . Count the ordered pairs $(A, B)$ such that $1 \le A, B \le (A \oplus B) \le N$ and $(A \oplus B) \notin S_1, \ldots, S_M$ .

For example, let $N = 10$ and $S = \{4, 6, 7, 10\}$ . There are 6 pairs $(A, B)$ that satisfy the condition.

$(1, 2)$ → $(1 \oplus 2) = 3$
$(1, 4)$ → $(1 \oplus 4) = 5$
$(1, 8)$ → $(1 \oplus 8) = 9$
$(2, 1)$ → $(2 \oplus 1) = 3$
$(4, 1)$ → $(4 \oplus 1) = 5$
$(8, 1)$ → $(8 \oplus 1) = 9$

The pair $(2, 4)$ does not satisfy the condition, since $(2 \oplus 4) = 6$ and $6 \in S$ . The pair $(5, 1)$ also fails, because it violates $A, B \le (A \oplus B)$ .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 10^6$ , $1 \le M \le 100\,000$ ). $N$ is the given bound, and $M$ is the size of the set $S_1, \ldots, S_M$ . The next line contains $M$ integers $S_i$ ( $1 \le S_i \le 10^6$ ), the elements of the set.

Output

Print one integer on a line: the number of pairs $(A, B)$ such that $1 \le A, B \le (A \oplus B) \le N$ and $(A \oplus B) \notin S_1, \ldots, S_M$ .

Examples4

Example 1
Input
```
10 4
4 6 7 10
```
Expected output
```
6
```
Example 2
Input
```
8 5
4 3 5 8 1
```
Expected output
```
10
```
Example 3
Input
```
20 7
3 7 18 15 12 18 19
```
Expected output
```
50
```
Example 4
Input
```
5 6
1 2 3 4 5 6
```
Expected output
```
0
```