Difficulty: Easy · LeetCode 338

Problem

Given n, return an array of length n+1 where result[i] is the number of 1-bits in i.

Understanding the problem

Right-shifting a number by 1 removes its last bit: num >> 1 has the same 1-bits as num minus the contribution of its last bit. So bits[num] = bits[num >> 1] + (num & 1) — build on already-computed results.

Intuition

DP recurrence: bits[num] = bits[num >> 1] + (num & 1). Removing the last bit gives a smaller number whose bit count is already known.

Approach

Initialize result = [0] * (n + 1).
For num in range(1, n+1):
result[num] = result[num >> 1] + (num & 1).
Return result.

Naive Solution — Brute Force

For each number 0..n, count its 1-bits independently using n & (n-1).

Python

class Solution:
    def countBits(self, n):
        result = []

        for num in range(n + 1):
            count = 0
            x = num

            while x:
                x &= x - 1
                count += 1

            result.append(count)

        return result

C++

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> result;

        for (int num = 0; num <= n; num++) {
            int count = 0;
            int x = num;

            while (x) {
                x &= x - 1;
                count++;
            }

            result.push_back(count);
        }

        return result;
    }
};

Java

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];

        for (int num = 0; num <= n; num++) {
            int count = 0;
            int x = num;

            while (x != 0) {
                x &= x - 1;
                count++;
            }

            result[num] = count;
        }

        return result;
    }
}

JavaScript

var countBits = function(n) {
    const result = [];

    for (let num = 0; num <= n; num++) {
        let count = 0;
        let x = num;

        while (x) {
            x &= x - 1;
            count++;
        }

        result.push(count);
    }

    return result;
};

Time: O(n log n) · Space: O(n) output

Optimized Code (Python 3)

Python

class Solution:
    def countBits(self, n):
        result = [0] * (n + 1)

        for num in range(1, n + 1):
            result[num] = (
                result[num >> 1]
                + (num & 1)
            )

        return result

C++

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> result(n + 1, 0);

        for (int num = 1; num <= n; num++) {
            result[num] = result[num >> 1] + (num & 1);
        }

        return result;
    }
};

Java

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];

        for (int num = 1; num <= n; num++) {
            result[num] = result[num >> 1] + (num & 1);
        }

        return result;
    }
}

JavaScript

var countBits = function(n) {
    const result = new Array(n + 1).fill(0);

    for (let num = 1; num <= n; num++) {
        result[num] = result[num >> 1] + (num & 1);
    }

    return result;
};

Time: O(n) · Space: O(n) output

Takeaway

Pattern — DP + bit shift: bits[num] = bits[num >> 1] + (num & 1)