338. Counting Bits

Problem Description

The problem states that given a non-negative integer n, we are required to find a list ans of length n + 1 where each element ans[i] represents the count of 1 bits in the binary representation of i. In other words, for every number from 0 to n, we need to calculate how many 1s are present in its binary form and store those values in an array.

Intuition

To understand the solution, it's important to grasp the concept of bit manipulation. In binary form, performing an & (bitwise AND) operation between a number i and i - 1 will result in a number that is the same as i but with its least significant 1 bit removed. For example, 10 in binary is 1010, and 9 is 1001; performing 1010 & 1001 equals 1000, which removes the least significant 1 bit in 1010.

Knowing this, we can build an array ans that uses this property to count the number of 1s. Start with ans[0] = 0 because the binary representation of 0 has zero 1 bits. Then, iterate through numbers from 1 to n, and for each number i, calculate ans[i] as ans[i & (i - 1)] + 1. Here, ans[i & (i - 1)] gives us the count of 1s for the number we get after removing the least significant 1 from i, and we add 1 because we've removed one 1 bit. This solution is efficient because it avoids recalculating the number of 1 bits for each number from scratch, using previous results instead.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution provided adopts a dynamic programming approach, where past information is reused to optimize the calculation of current values. The algorithm uses a simple but powerful bit manipulation trick based on the property that for any given number i, the number i & (i - 1) results in i with the least significant 1 bit turned off. With this, we can recursively calculate the number of 1 bits for i if we already know the number of 1 bits for i & (i - 1).

Here are the steps involved in the solution:

Initialize the array ans to have length n + 1, all initialized to 0. This array is to hold the count of 1 bits for each index, which corresponds to a number from 0 to n.
Start a loop from 1 up to n because we already know ans[0] is 0:
- Inside the loop, for each number i, assign ans[i] = ans[i & (i - 1)] + 1.
  - Here, i & (i - 1) is the previously mentioned bit manipulation, which gives us a number less than i, which has one less 1 bit.
  - We then take the count of 1s for that number (ans[i & (i - 1)]), which we've already calculated, and add 1 to account for the 1 bit we've just stripped off.
  - Hence, ans[i] accurately stores the count of 1 bits for the number i.
After the loop completes, return the ans array. It now contains the number of 1s in the binary representation of each number from 0 to n.

This algorithm runs in O(n) time because it computes each entry in ans in constant time relative to i. The space complexity is also O(n), as additional storage proportional to the input size is created for the ans array. No other data structures are used, and the problem does not require any other specific algorithms or complex patterns.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have n = 5. Our goal is to find out how many 1 bits are present in the binary representation of numbers 0 to 5 and store it in an array ans.

Initialize ans to an array of length n + 1, filled with zeros: ans = [0, 0, 0, 0, 0, 0].
Now perform the loop from 1 to n and fill in the ans array:
- i = 1: The binary representation of 1 is 1. Using the formula ans[i] = ans[i & (i - 1)] + 1 means:
  - ans[1] = ans[1 & 0] + 1 = ans[0] + 1 = 0 + 1 = 1.
  - So, ans is now [0, 1, 0, 0, 0, 0].
- i = 2: The binary representation of 2 is 10. Using the formula:
  - ans[2] = ans[2 & 1] + 1 = ans[0] + 1 = 0 + 1 = 1.
  - So, ans is now [0, 1, 1, 0, 0, 0].
- i = 3: The binary representation of 3 is 11. Using the formula:
  - ans[3] = ans[3 & 2] + 1 = ans[2] + 1 = 1 + 1 = 2.
  - So, ans is now [0, 1, 1, 2, 0, 0].
- i = 4: The binary representation of 4 is 100. Using the formula:
  - ans[4] = ans[4 & 3] + 1 = ans[0] + 1 = 0 + 1 = 1.
  - So, ans is now [0, 1, 1, 2, 1, 0].
- i = 5: The binary representation of 5 is 101. Using the formula:
  - ans[5] = ans[5 & 4] + 1 = ans[4] + 1 = 1 + 1 = 2.
  - So, ans is now [0, 1, 1, 2, 1, 2].
Our final ans array is [0, 1, 1, 2, 1, 2], which represents the count of 1 bits in the binary representations of the numbers from 0 to 5.

As we can see from this example, we successfully calculated the count of 1 bits for each number without recalculating from scratch each time. Instead, we relied on previously computed values to determine the count of 1s for each subsequent number. The result is a highly efficient algorithm with O(n) time complexity and O(n) space complexity.

Solution Implementation

1class Solution:
2    def countBits(self, num: int) -> List[int]:
3        # Create a list initialized with zeros for all elements up to num
4        bit_counts = [0] * (num + 1)
5      
6        # Loop through all numbers from 1 to num
7        for i in range(1, num + 1):
8            # Use the bit count of the previous number that has the same bits
9            # except the last set bit (i & (i - 1)) and add 1 for the last set bit
10            # This works because i & (i - 1) drops the lowest set bit of i
11            # For example, if i = 10100 (binary), i & (i - 1) = 10000, which is i without the last set bit.
12            # ans[i & (i - 1)] already contains the count of 1s for 10000,
13            # so we just need to add 1 for the dropped bit to get the count for 10100.
14            bit_counts[i] = bit_counts[i & (i - 1)] + 1
15      
16        # Return the list of bit counts for all numbers from 0 to num
17        return bit_counts
18

1class Solution {
2    public int[] countBits(int n) {
3        // Create an array 'bitCounts' of size n+1 to hold the number of 1s for each number from 0 to n.
4        int[] bitCounts = new int[n + 1];
5      
6        // Iterate over each number from 1 to n to calculate bit count.
7        for (int i = 1; i <= n; ++i) {
8            // Use the previously computed results to find the current number's bit count.
9            // 'i & (i - 1)' drops the lowest set bit of i. So 'bitCounts[i & (i - 1)]' gives us
10            // the count of bits for the current number without the lowest set bit.
11            // Then, we add 1 for the dropped bit to get the final count for the current number.
12            bitCounts[i] = bitCounts[i & (i - 1)] + 1;
13        }
14      
15        // Return the populated array containing bit counts for all numbers from 0 to n.
16        return bitCounts;
17    }
18}
19

1#include <vector>  // Include the vector header for using the std::vector class
2
3class Solution {
4public:
5    // This function generates a vector containing the number of 1-bits for all numbers from 0 to n
6    vector<int> countBits(int n) {
7        vector<int> bitCounts(n + 1); // Initialize a vector to store the count of 1-bits for each number
8
9        for (int num = 0; num <= n; ++num) {
10            // Use the built-in function __builtin_popcount to count the number of 1-bits in the binary representation of num
11            bitCounts[num] = __builtin_popcount(num);
12        }
13
14        return bitCounts; // Return the vector of bit counts
15    }
16};
17

1// This function calculates the number of 1-bits for every number from 0 to n and returns them as an array.
2// Each array index corresponds to a number, and its value is the count of 1s in the binary representation.
3function countBits(n: number): number[] {
4    // Initialize an array to store the bit counts with a size of n + 1, filled with zeros.
5    const bitCounts: number[] = new Array(n + 1).fill(0);
6
7    // Loop from 1 to n to calculate bit counts.
8    for (let i = 1; i <= n; ++i) {
9        // The number of bits in the current number is equal to the number of bits in the number obtained 
10        // by turning off the rightmost 1-bit in i's binary representation, i.e., i & (i - 1), 
11        // and then adding 1 (since we've removed one bit).
12        bitCounts[i] = bitCounts[i & (i - 1)] + 1;
13    }
14
15    // Return the array containing bit counts for all numbers from 0 to n.
16    return bitCounts;
17}
18

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Time and Space Complexity

The time complexity of the provided code is O(n). This is because the loop runs from 1 to n, and within the loop, the operation i & (i - 1) is computed in constant time, as well as the increment + 1. Thus, the loop constitutes the main factor in the time complexity, which linearly depends on n.

The space complexity is also O(n). The additional space is used to store the result in the list ans, which contains n + 1 elements. Apart from the ans list, only a constant amount of extra space is used for indices and temporary variables in the loop.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Fast-slow pointersTwo pointers moving in opposite directionBinary searchDepth first search

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

338. Counting Bits

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings