Clean solution with binary search
Notice that:\nnumber of set bits in (a OR b) and (a AND b) = number of set bits in a + number of set bits in b\n\nclass Solution {\n    func countExcellentPairs
Notice that:\nnumber of set bits in (a OR b) and (a AND b) = number of set bits in a + number of set bits in b\n```\nclass Solution {\n    func countExcellentPairs(_ nums: [Int], _ k: Int) -> Int {\n        // distinct numbers\n        let set = Set<Int>(nums)\n        let n = set.count\n        \n        // store the number of `1` bit of each item in the set  \n        var array = Array(repeating: 0, count: n) \n        var i = 0\n        for num in set {\n            var num = num\n            var count = 0\n            while num > 0 {\n                count += num & 1\n                num = num >> 1\n            }\n            array[i] = count\n            i += 1\n        }\n        \n        var res = 0\n        let sorted = array.sorted()\n        for i in 0..<n {\n            // Use binary search to find the index of the smallest number which satisfy the condition.\n            var left = 0\n            var right = n-1\n            var id = -1\n            while left <= right {\n                let mid = left + (right - left) / 2\n                if sorted[i] + sorted[mid] >= k {\n                    id = mid\n                    right = mid - 1\n                } else {\n                    left = mid + 1\n                }\n            }\n            if id != -1 { // found the index\n                res += n - id\n            }\n        }\n        return res\n    }\n}\n```
[]