java binarySearch
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```\nclass Solution {\n    \n    public  long countExcellentPairs(int[] nums, int k) {\n\n        // 1. bitCount(num1 and num2) + bitCount(num1 or num2) = bitCount(num1) + bitCount(num2) \uC774\uB2E4. \n        //   \u203B or\uC5D0\uC11C \uC0C8\uB85C \uD569\uCCD0\uC9C0\uB294 \uAC83\uC740 and\uB54C \uD569\uCCD0\uC9C0\uC9C0 \uC54A\uACE0 or\uC5D0 \uC911\uBCF5\uB418\uB294 \uAC83\uC740 and\uB54C \uB354\uD574\uC9C4\uB2E4.\n\n        // 2. \uC911\uBCF5\uB418\uB294 \uC22B\uC790\uAC00 \uC5C6\uB3C4\uB85D set\uC744 \uC774\uC6A9\uD574 \uC911\uBCF5\uC744 \uC81C\uAC70\uD558\uACE0 list\uC5D0 nums[i]\uB97C bitcount \uD615\uD0DC\uB85C \uBCC0\uD658\uD574\uC11C \uC800\uC7A5\uD55C\uB2E4.\n\n        // 3. list\uC815\uB82C\n\n        // 4. list\uB97C \uC21C\uD68C\uD558\uBA74\uC11C \n        //    1) binarySearchUpper\uB85C list\uC5D0\uC11C k- \uD604\uC7AC bit\uC218(list.get(i))\uC758 index\uB97C \uCC3E\uB294\uB2E4.\n        //    2) \uCC3E\uC740 index\uAC00 i(\uC2DC\uC791\uC9C0\uC810)\uC774\uBA74 \uAC19\uC740 \uC22B\uC790\uB07C\uB9AC\uC758 pair\uC774\uB2C8 1\uB9CC \uB354\uD574\uC8FC\uBA74\uB418\uACE0 index\uB97C \uD558\uB098 \uC99D\uAC00\uC2DC\uCF1C\uC900\uB2E4.\n        //    3) index ~ list\uB9C8\uC9C0\uB9C9 \uC758 \uAE38\uC774 * 2(\uC21C\uC11C\uAC00 \uB2E4\uB978 pair) \uB97C \uB354\uD574\uC900\uB2E4.\n\n        // 5.  result \uBC18\uD658\n\n         Set<Integer> set = new HashSet<Integer>();\n\n        List<Integer> list = new ArrayList<Integer>();\n\n        for(int i = 0; i < nums.length; i++) {\n            if ( !set.contains(nums[i]) ) {\n                set.add(nums[i]);\n\n                list.add(Integer.bitCount(nums[i]));\n            \n            }\n        }\n\n        \n\n        Collections.sort(list, new Comparator<Integer>() {\n\n            @Override\n            public int compare(Integer arg0, Integer arg1) {\n                return arg0-arg1;\n            }\n            \n        });\n\n        // System.out.println(list);\n\n        long result = 0;\n        for(int i = 0; i <  list.size(); i++) {\n            int bitCount = list.get(i);\n\n            int idx = binarySearchUpper(list, i, k - bitCount);\n\n            if ( idx == list.size() ) continue;\n            if ( idx == i ) {\n                result++;\n                idx++;\n            }\n\n            result += (list.size()-idx) * 2;\n\n        }\n        \n        return result;\n    }\n\n    private  int binarySearchUpper(List<Integer> list, int start,  int target) {\n        int end = list.size();\n        int mid;\n\n        while(start < end) {\n            mid = (start + end)/2;\n\n            if ( list.get(mid) >= target ) {\n                end = mid;\n            } else{\n                start = mid+1;\n            }\n        }\n\n        return end;\n    }\n}\n```
['Binary Search', 'Java']