a
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.Arrays;\nimport java.util.HashMap;\nimport java.util.HashSet;\n\nclass Solution {\n\n    // https://leetcode.com/problems/number-of-excellent-pairs/submissions/\n\n\n    // approach 2 O(NLogN)\n    public long countExcellentPairs(int[] nums, int k) {\n        long cnt = 0;\n\n        // remove duplicates\n        HashSet<Integer> dedupedNums = new HashSet<>();\n        for (int num : nums) {\n            dedupedNums.add(num);\n        }\n        int n = dedupedNums.size();\n        long[] bits = new long[n];\n        int m = 0;\n        for (int num : dedupedNums) {\n            long numBits = Integer.bitCount(num);\n            bits[m] = numBits;\n            m++;\n        }\n        Arrays.sort(bits);\n        // IDEA: maintain sorted array of the number of bits of each unique number\n\n        System.out.println("BITS: " + Arrays.toString(bits));\n\n        // use 2 pointers to calculate all valid pairs\n        // in the sorted array of bitCounts\n        // 2 pointers allow us to pass the array once with each pointer (simultaneously)\n        // and this way find all pairs in O(N) instead of O(N^2)\n\n        // start second pointer at the back\n        int j = n - 1;\n        for (int i = 0; i < n; i++) {\n            if (bits[i] * 2 >= k) {\n                cnt++;\n            }\n            \n            // we check the current j and if it is valid, we go in the loop\n            // we immediately mark the next j to check\n            // since the logic below uses all elements AFTER j to calculate\n            // logic: find the first j that is not valid: all after it are valid\n            while (j >= 0 && bits[i] + bits[j] >= k) {\n                j--;\n            }\n\n\n            // count each pair twice since (a,b) and (b,a) are both valid\n            if (j >= i) {\n                // all after j, up to and including the last index\n                cnt += ((n - 1) - j) * 2;\n            } else { // j < i\n                // all after i, up to and including the last index\n                cnt += ((n - 1) - i) * 2;\n            }\n        }\n        return cnt;\n    }\n\n//    public long countExcellentPairs(int[] nums, int k) {\n//        long cnt = 0;\n//\n//        // remove duplicates\n//        HashSet<Integer> dedupedNums = new HashSet<>();\n//        for (int num : nums) {\n//            dedupedNums.add(num);\n//        }\n//        // count the number of elems with specific number of bits\n//        // then the number of pairs (bits1,bits2) where sum >= k\n//        // is equal to the number of possible a\'s with bits1 * number of possible b\'s with bits2\n//        // this covers the cases of (bits1,bits1) where bits(a) * 2 >= k\n//        // e.g. we have a1 with 2 bits and a2 with 2 bits:\n//        // pairs are:\n//        // (a1,a1)\n//        // (a2,a2)\n//        // (a1,a2)\n//        // (a2,a1)\n//        // or (2,2) = 2 * 2 = 4\n//        HashMap<Long, Long> numBitsToCount = new HashMap<>();\n//        for (int num : dedupedNums) {\n//            long numBits = Integer.bitCount(num);\n//            numBitsToCount.put(numBits, numBitsToCount.getOrDefault(numBits, (long) 0) + 1);\n//        }\n//        for (long bits1 : numBitsToCount.keySet()) {\n//            for (long bits2 : numBitsToCount.keySet()) {\n//                if (bits1 + bits2 < k) continue;\n//\n//                cnt += numBitsToCount.get(bits1) * numBitsToCount.get(bits2);\n//            }\n//        }\n//        return cnt;\n//    }\n\n//    int countBits(int num) {\n//        int cnt = 0;\n//        while (num != 0) {\n//            cnt += num & 1;\n//            num = num >> 1;\n//        }\n//        return cnt;\n//    }\n}\n```
['Java']