Brute Force O(n*n*number) to Optimized O(n*log(number)) code with all the logics and algorithms used
1. Brute Force Code\n### Approach\nChecking all the possible pairs along with trivial function to finds the count of set bits in binary representation of a deci
# 1. Brute Force Code\n### Approach\nChecking all the possible pairs along with trivial function to finds the count of set bits in binary representation of a decimal number.\n\n### Complexity\n- Time complexity: O(n * n * number)\n\n- Space complexity: O(n * 2)\n\n```\nclass Solution {\n    private static int countSetBits(int number){\n        int count = 0;\n        for(int bit=1;bit<=32;bit++){\n            count += (number & 1);\n            number >>= 1;\n        }\n        return count;\n    }\n\n    public long countExcellentPairs(int[] nums, int k) {\n        Set<List<Integer>> set = new HashSet<>();\n        for(int index1=0;index1<nums.length;index1++){\n            for(int index2=0;index2<nums.length;index2++){\n                int num1 = (nums[index1]|nums[index2]), num2 = (nums[index1]&nums[index2]);\n                int setBitsInNum1 = countSetBits(num1), setBitsInNum2 = countSetBits(num2);\n                if(setBitsInNum1 + setBitsInNum2 >= k){set.add(Arrays.asList(nums[index1],nums[index2]));}\n            }\n        }\n        return (long)set.size();\n    }\n}\n\n// Brute Force Approach - TLE\n// Time Complexity : O(n*n*number)\n// Space Complexity : O(n*2)\n```\n \n\n# 2. Brute Force Code With countBits Function Optimization \n### Approach\nChecking all the possible pairs along with Brian Kernighan\u2019s Algorithm to finds the count of set bits in binary representation of a decimal number instead of using trivial function.\n\n### Complexity\n- Time complexity: O(n * n * log(number))\n\n- Space complexity: O(n * 2)\n```\nclass Solution {\n\n    // Brian Kernighan\u2019s Algorithm\n    private static int countSetBits(int number){\n        int count = 0;\n        while(number != 0){\n            number = (number)&(number-1);\n            count++;\n        }\n        return count;\n    }\n\n    public long countExcellentPairs(int[] nums, int k) {\n        Set<List<Integer>> set = new HashSet<>();\n        for(int index1=0;index1<nums.length;index1++){\n            for(int index2=0;index2<nums.length;index2++){\n                int num1 = nums[index1], num2 = nums[index2];\n                int setBitsInNum1 = countSetBits(num1), setBitsInNum2 = countSetBits(num2);\n                if(setBitsInNum1 + setBitsInNum2 >= k){set.add(Arrays.asList(nums[index1],nums[index2]));}\n            }\n        }\n        return (long)set.size();\n    }\n}\n\n// Brute Force Approach - TLE\n// Time Complexity : O(n*n*log(number))\n// Space Complexity : O(n*2)\n\n```\n\n# 3. Code By Storing The setBits \n### Approach\nStoring The setBits Of All The Numbers Of The Array And THen Applying The Two Sum Analogy.\n\n### Complexity\n- Time complexity: O(n * n * log(number))\n\n- Space complexity: O(n *2)\n```\nclass Solution {\n\n    // Brian Kernighan\u2019s Algorithm\n    private static int countSetBits(int number){\n        int count = 0;\n        while(number != 0){\n            number = (number)&(number-1);\n            count++;\n        }\n        return count;\n    }\n\n    private static int[] storeSetBits(int[] nums){\n        int[] store = new int[nums.length];\n        for(int index=0;index<nums.length;index++){store[index] = countSetBits(nums[index]);}\n        return store;\n    }\n\n    private static long twoSumAnalogy(int[] nums, int[] store, int target){\n        Set<List<Integer>> set = new HashSet<>();\n        for(int index1=0,len=store.length;index1<len;index1++){\n            for(int index2=0;index2<len;index2++){\n                if(store[index1] + store[index2] >= target){\n                    set.add(Arrays.asList(nums[index1],nums[index2]));\n                }\n            }\n        }\n        return (long)set.size();\n    }\n\n    public long countExcellentPairs(int[] nums, int k) {\n        int[] store = new int[nums.length];\n        store = storeSetBits(nums);\n        return twoSumAnalogy(nums,store,k);\n    }\n}\n\n// Brute Force Approach - TLE\n// Time Complexity : O(n*n*log(number))\n// Space Complexity : O(n*2)\n\n```\n\n# 4. Optimized Code Using The Counting Sort \n### Approach\n- The Inclusion-Exclusion Principle\n```\nbits(num1 OR num2) + bits(num1 AND num2) = bits(num1) + bits(num2)\n```\n- Working \n\n    For all different ```a``` in ```nums```, counts its number of bits.\n\n    Enumearte the number of bits ```k1``` and ```k2```,\n    if ```k1 + k2 >= k```, we accumulate ``` count[k1] * count[k2] ```.\n- Why we made countArray of size 30?\n    Because it is given that ```max(nums[i]) = 1e9```, and we knwo that to represent any number in binary we needs a maximum of ```[log2(number)] + 1``` bits. Hence ```log2(10^9) ~ 9*log2(10) ~ 9*3.322 ~ 29.8 => [29.8] + 1 = 30```.\n\n### Complexity\n- Time complexity: O(n * log(number))\n\n- Space complexity: O(n)\n```\nclass Solution {\n    public long countExcellentPairs(int[] nums, int k) {\n        long countArray[] = new long[30], count = 0;\n        Set<Integer> set = new HashSet<>(); \n        for(int num : nums) set.add(num);                                    // O(n)    \n        for(int num : set) countArray[Integer.bitCount(num)]++;              // O(nlog(number))\n        for(int bit=1;bit<30;bit++){\n            for(int bit_=1;bit_<30;bit_++){\n                if(bit+bit_>=k) count += countArray[bit]*countArray[bit_];\n            }\n        }\n        return count;\n    }\n}\n\n// Counting Sort Optimized Code \n// Time Complexity : O(n + nlog(number))\n// Space Complexity : O(n) \n\n```
['Java']