← Math

Count Bits DP

Easy
Python
def count_bits(n):
    return [bin(i).count('1') for i in range(n+1)]
Java
public int[] countBits(int n){
    int[] dp=new int[n+1];
    for(int i=1;i<=n;i++) dp[i]=dp[i>>1]+(i&1);
    return dp;
}

Key Insight

Python bin(i).count('1') is concise. Java DP: dp[i]=dp[i/2]+(i%2).

Python → Java Differences

  • Python bin().count() vs Java DP
  • i>>1 is i//2
  • i&1 is i%2
Python
def count_bits(n):
    return [bin(i).count('1') for i in range(n+1)]
Java
public int[] countBits(int n){
    int[] dp=new int[n+1];
    for(int i=1;i<=n;i++) dp[i]=dp[i>>1]+(i&1);
    return dp;
}

Algorithm Steps

1. Count bits for each number
← Previous All Math Next →