> For the complete documentation index, see [llms.txt](https://code-render.gitbook.io/leetcode-editorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-render.gitbook.io/leetcode-editorials/09-september/01.counting-bits.md).

# 01. Counting Bits

The problem can be found at the following link: [Question Link](https://leetcode.com/problems/counting-bits/?envType=daily-question\&envId=2023-09-01)

## My Approach

There are two methods to solve this problem

### 1. We can count number of bits by iterating every number till n and count each set bits in every number

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(nlogn)`
* **Auxiliary Space Complexity**: `O(1)`

## Code (C++)

```cpp
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        for(int i=0;i<=n;i++){
            int x = i;
            int one =0;
            while(x){
                if(x&1) one++;
                x /=2;
            }
            ans.push_back(one);
        }
        return ans;
    }
};
```

### 2. Optimized approch

Let if we have X and Y in Such a way that, `X/2 = Y` then Number of set bits in X - Number of set bit in Y <= 1

```plaintext
eg let X = 7and Y = 3
then 7 / 2 = 3;

7 -> 1 1 1 number of set bit are 3
3 -> 0 1 1 number of set bit are 2

there difference is 3 - 2 <= 1

another eg
X = 12 and y = 6
then 12 / 2 = 6;

12 -> 1100 number of set bit are 2
6 -> 0110 number of set bit are 2

there difference is 2 - 2 <= 1
```

There can be 2 cases whether X is Odd or Even

1. if X is ODD

then the (LSB) Least Significant Bit will always be set and dividing by 2 means right shifting the number by 1 bit. so if last bit is set and right shift it by 1 bit than the last set bit will be lost. therfore the new number Y has 1 set bit less than in compare to X

2. if X is Even

then LSB will be equal to 0, therefore even we do right shift by1 bit then only this 0 bit will be lost and no set bit got lost so When we have X has Even,

no of set bit in X = no of set bit in Y and When X is ODD

no of set bit in X = 1 + no of set bit in Y

## Time and Auxiliary Space Complexity

* **Time Complexity**: `O(n)`
* **Auxiliary Space Complexity**: `O(1)`

## Code (C++)

```cpp
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n+1);
        ans[0] = 0;

        for(int i=1;i<=n;i++){
            ans[i] = ans[i/2] + i%2;
        }
        return ans;
    }
};
```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://leetcode.com/discuss/general-discussion). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [rishabhv12/Daily-Leetcode-Solution](https://github.com/rishabhv12/Daily-Leetcode-Solution) repository.