Use the recurrence: popcount(i) = popcount(i >> 1) + (i & 1). Shifting right drops the last bit, and the AND captures it.

Counting Bits

easy

Acceptance: 65%

Bit ManipulationDynamic Programming

Given a non-negative integer n, produce an array of length n + 1 in which the value at index i equals the number of 1-bits in the binary representation of i.

Examples

Example 1:

Input:n = 3

Output:[0,1,1,2]

Example 2:

Input:n = 7

Output:[0,1,1,2,1,2,2,3]

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Counting Bits

Examples

Hints

Related Problems