Swift | FULLY EXPLAINED
Brute Force approach O(n^2)  (Time Limit Exceeded)\n\nclass Solution {\n    func countExcellentPairs(_ nums: [Int], _ k: Int) -> Int {\n        let nums = Set(n
**Brute Force approach O(n^2)  (Time Limit Exceeded)**\n```\nclass Solution {\n    func countExcellentPairs(_ nums: [Int], _ k: Int) -> Int {\n        let nums = Set(nums).map { $0.nonzeroBitCount }\n        var counter = 0\n        for i in nums {\n            for j in nums where i + j >= k {\xA0\n                counter += 1\n            }\n        }\n        return counter\n    }\n}\n```\n\n**Optimized approach O(n)  (Accepted Answer)**\n```\nclass Solution {\n    func countExcellentPairs(_ nums: [Int], _ k: Int) -> Int {\n        let nums = Set(nums).map{ $0.nonzeroBitCount }.sorted()\n        var counter = nums.reduce(0) { $0 + ($1*2 >= k ? 1 : 0) } \n        var left = 0, right = nums.count - 1\n        while left < right {\n            if nums[left] + nums[right] >= k {\n                counter += (right - left) * 2\n                right -= 1\n            } else {\n                left += 1\n            }\n        }\n        return counter\n    }\n}\n```\n\n**OPTIMIZED SOLUTION EXPLANATION**\n\n**1) Rewrite Problem Statement**\n\nThe problem expects us to find pairs (or single elements doubled up) where the bit counts of `OR`ing and `AND`ing add up to at least `k`:\n\n```\ncountbits(nums[i] | nums[j]) + countbits(nums[i] & nums[j]) >= k\n```\n\nMathematically, this is a disguised version of simple addition:\n\n```\ncountbits(nums[i]) + countbits(nums[j]) >= k\n```\n\nWe can use the simple addition approach to rewrite the problem statement with two requirements:\n**Requirement 1)** We want to count each unique individual element whose bit count doubled up is greater than or equal to `k`\n**Requirement 2)** We want to count each unique distinct pair of elements whose bit counts added together is greater than or equal to `k`. Each distinct pair counts twice to the solution, e.g`(nums[i], nums[j])` and `(nums[j], nums[i])` since both need to be included in the count.\n\n**2) Implement Solution**\n1) Create an array of unique elements of `nums`. In Swift, this is easy to do: `Array(Set(nums))`\n2) Convert all elements in the set to bit counts. Also, easy: `.map { $0.nonzeroBitCount }`. Since this uses a Swift library function to count bits, we may get asked to count bits in hand-generated code: \n```\n.map{ num -> Int in\n\tvar count = 0, num = num\n\twhile num > 0 {\n\t\tcount += num & 1\n\t\tnum >>= 1\n\t}\n\treturn count\n }\n```\n3) Finally, this unique element bit count array needs to be sorted so we can optimize the naive ***O(n^2)*** algorithm to an ***O(n)*** algorithm.\n\nSteps 1 - 3 can be written in one line:\n```\nlet nums = Set(nums).map{ $0.nonzeroBitCount }.sorted()\n```\n\n4) Next, we can implement **Requirement 1** by counting up how many individual element bit counts in `nums`, when doubled, are at least `k`:\n```\nvar counter = nums.reduce(0) { $0 + ($1*2 >= k ? 1 : 0) } \n```\nor, alternatively:\n```\nvar counter = nums.filter { $0*2 >= k }.count \n```\n\n5) Next, we can implement **Requirement 2** with a ***O(n)*** algorithm that uses a sliding window technique. There is a low pointer `left` and a high pointer `right`. If `nums[left] + nums[right] >= k`, then we also know that every element between `left + 1` and `right - 1` when added to `nums[right]` will also be greater than or equal to `k` . When this is the case we add `left-right` to our `counter`, and then multiply by two because both permutations are required to be counted in the result.\n6) The `left` and `right` pointers are stepped incrementally, instead of half-wise like a binary search, so the complexity order is ***O(n)*** instead of ***O(log2 n)*** . \n7) When the `left` and `right` pointers converge, we are finished and return `counter`.
[]