Counting Bits LeetCode

 Problem Link:

https://leetcode.com/problems/counting-bits/

Solution 1 :

public int cal(int n){

         int count=0;

         while(n>0){

             n=n&(n-1);

             ++count;

         }

         return count;

     }

         

    public int[] countBits(int n) {

        int arr[]=new int[n+1];

        for(int i=0;i<=n;i++){

            arr[i]=cal(i);

        }

        return arr;

    }

Time Complexity:O(N*number of set bits in number)[LeetCode Time: 2ms faster than 68.42%]

Space Complexity:O(1)[No array or any other data structure is used.]

Auxillary Space:O(N) [An additional array is used which will be returned later.]

LeetCode Memory:43MB less than 84.07%.

Total Test Cases:15

Approach :

Here we will send every element to the cal function as a parameter and later using the Brian-Kerningam algorithm we will calculate the number of set bits in a number.

The count of set bits will be then stored in an array against that particular index and that array will be returned later. 

-----------------------------------------------------------------------------------------------------------------------------

Solution 2:

 public int[] countBits(int n) {

        int arr[]=new int[n+1];

        for(int i=0;i<=n;i++){

            arr[i]=Integer.bitCount(i);

        }

        return arr;

    }  

Time Complexity:[LeetCode Time: 4ms faster than 36.57%]

Space Complexity:O(1)[No array or any other data structure is used.]

Auxillary Space:O(N)[ An additional array is used which will be returned later.]

LeetCode Memory:44.8MB less than 47.83%.

Total Test Cases:15

Approach :

Here We use the inbuilt function provided by java to count the number of set bits.

And while traversing from 0 to n+1 we store the set count of every digit in arr at that particular index.

Later return an array.

-----------------------------------------------------------------------------------------------------------------------------

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"