Problem statement

https://leetcode.com/problems/count-pairs-with-xor-in-a-range/

Solution

First idea is to look for number less than T, not in range.

Second idea is imagine we have 10110, then numbers smaller than this can be in one of groups, where we use idea of digits build: ? can be any digit here.

1010?

100??

0????

The idea is to calculate counter of nums first and then on each iteration recalculate it, using count[a] + count[a^1] for number a >> 1.

Complexity

Time complexity will be O(min(m, n * log(2m/n)), where n is length of nums and m is maximum among nums. The idea is that on first level we can have no more than m elements in counter and on each next iteration it can be no more than m/2 and so on. From another point of view on first level we have n values and on each next log(m/n) levels we can have again no more than n, until we reach n bits, and then no more than n/2 and so on. Space complexity is O(n).

Code

#### borrowed code
class Solution:
    def countPairs(self, nums, low, high):
        def test(x):
            count, res = Counter(nums), 0
            while x:
                if x & 1:
                    res += sum(count[a] * count[(x^1) ^ a] for a in count)
                count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
                x >>= 1
            return res // 2
        return test(high + 1) - test(low)

Remark

Alternative solution is to use Tries: put all numbers in Trie and then for each possible start from digits build, for example 100.., consider all 2^3 possible starts and check how many elements in our Trie we have such that xor is equal to 100. Time complexity will be O(n log m)