python | O(nlogn) sorting + binary search solution explained
For me, the key insight into this problem was the realization that the test we were provided to determine if a pair is excellent can be greatly simplified. The 
For me, the key insight into this problem was the realization that the test we were provided to determine if a pair is excellent can be greatly simplified. The alternate test the simplification leads to can then be reverse to quickly construct and count excellent pairs.\n\n## Checking if a Pair is Excellent\nBefore discussing how to simplify the test, I want to define a couple functions which will be helpful in this discussion:\n* **bits(n) = {the set of all \'1\' bits in the binary representation of n}**\n* **f(m, n) = |bits(m | n)| + |bits(m & n)|**\nwhere |A| is the number of elements in the set A, | is bitwise OR, and & is bitwise AND\n(also note that a pair (m, n) is excellent if f(m, n) >= k)\n\n\nNext, for a bit to be in bits(m | n) it must either be in bits(m) or bits(n). This means that **bits(m | n) = bits(m) \u222A bits(n)**. From here we can compute an alternate method to compute the size of this set, since **|bits(m) \u222A bits(n)| = |bits(m)| + |bits(n)| - |bits(m) \u2229 bits(n)|**. (basically, this means that the size of the set (bits(m) \u222A bits(n)) is the size of bits(m) plus the size of bits(n) minus any double-counting)\n\nThen, for a bit to be in bits(m & n) it must be in both bits(m) and bits(n). Or, in set notation: **bits(m & n) = bits(m) \u2229 bits(n)**. This means that **|bits(m & n)| = |bits(m) \u2229 bits(n)|**.\n\nSubbing these results into our original expression for f(m, n) gives:\n\n**f(m, n) = |bits(m | n)| + |bits(m & n)| = |bits(m)| + |bits(n)| - |bits(m) \u2229 bits(n)| + |bits(m) \u2229 bits(n)|**\n\nAnd finally, the intersection terms cancel out, leaving:\n\n**f(m, n) = |bits(m)| + |bits(n)|**\n\nThis equation is nice, because it implies that f(m, n) doesn\'t include any difficult interations between the bits of m and n, instead it only depends on how many \'1\' bits are in m and n separately, which is a much easier function to work with.\n\n## The Algorithm\nPrecomputation: O(nlogn)\n1. Throw out any duplicates since we only care about unique pairs.\n2. Compute the number of \'1\' bits for each number in nums. I\'ll call the resulting list *B*.\n3. Count the number of occurences of each value *b* in *B*. This will give us a list *counts* which contains tuples of (# bits, occurences).\n4. Sort *counts* for easier lookup later (either with a bianry sort, or a 2-pointer approach).\n5. Compute the reversed prefix sum of the occurences. This is useful, because if a collection of numbers with i bits and a collection of numbers with j bits has k or more bits, then every collection of numbers with more than j bits will also form valid pairs with numbers with i bits. So pre-computing this avoids expensive re-computation later. In my code I called this array *sums* for lack of a better name.\n\nPair Counting: O(nlogn)\n1. Select a *(b, c) = (# bits, occurences)* item from *counts*.\n2. Use a bisection search on counts to find the index *i* of the smallest existing group of numbers which for excellent pairs with numbers containing *b* bits (i.e. the smalles *i* such that b + counts[i][0] >= k).\n3. Compute the number of valid pairs which can be made where the first number has *b* bits using the expression: *c\\*sums[i]* (i.e. to make a valid group you can choose any number with *b* bits, and any number with at least *k - b* bits, so the number of pairs which start with *b* bits is equal to the number of numbers with *b* bits times the number of numbers with at least *k - b* bits).\n4. Repeat steps 1-3 for all items in *counts*, summing the result.\n\n## Code\nFirst Run Performance: 1102 ms / 32 MB\nTime Complexity: O(nlogn)\nSpace Complexity: O(n)\n\'\'\'\n\n\tclass Solution:\n\t\tdef countExcellentPairs(self, nums: List[int], k: int) -> int:\n\t\t\t# Count the Number of Bits in Each Unique Number - O(n)\n\t\t\t# Tally the Number of Times Each Bit Count Occurs - O(n)\n\t\t\t# Sort the (bit count, tally) pairs by bit count - O(nlogn)\n\t\t\tcounts = sorted(Counter(map(int.bit_count, set(nums))).items()) # (I am fully aware that this line of code is really doing too much work)\n\n\t\t\t# Compute the Reversed Prefix Sum of the Tallies (i.e. sums[i] is how many numbers have at least counts[i][0] \'1\' bits) - O(n)\n\t\t\tsums = [0]*len(counts)\n\t\t\tsums[-1] = counts[-1][1]\n\t\t\tfor i in range(len(sums) - 2, -1, -1):\n\t\t\t\tsums[i] += counts[i][1] + sums[i + 1]\n\n\t\t\t# Choose Each Number as the First Number of a Pair - O(nlogn)\n\t\t\tpairs = 0\n\t\t\tfor n, c in counts:\n\t\t\t\t# Find the Smallest Number Which Forms a Valid Pair - O(logn)\n\t\t\t\ti = bisect_left(counts, k - n, key = lambda x: x[0])\n\n\t\t\t\t# Check if Any Pairs Can be Formed\n\t\t\t\tif i < len(sums):\n\t\t\t\t\t# Compute the Number of Pairs Which Start With the Given Collection of Numbers\n\t\t\t\t\tpairs += c*sums[i]\n\n\t\t\t# Return the Number of Pairs\n\t\t\treturn pairs\n\'\'\'\n\n## Notes\nThe pair counting can also be done with a 2-pointer approach, which reduces the time complexity for that section to O(n), since each pointer makes exactly 1 pass through *counts*.
['Sorting', 'Binary Tree', 'Python', 'Python3']