package Leetcode.BitManipulation;

import java.util.Arrays;

/**
 * @author zhengstars
 * @date 2024/06/09
 */
public class CountingBits {
    public static int[] countBits(int n) {
        // Initialize the result array with length n + 1.
        int[] ans = new int[n + 1];

        // Loop through the numbers from 1 to n.
        for (int i = 1; i <= n; i++) {
            // The number of 1's in the binary representation of i is equal to:
            // the number of 1's in i / 2 (i.e., i >> 1) plus
            // 1 if the least significant bit of i is 1 (i.e., i & 1).
            // This is based on the dynamic programming principle where the solution
            // for a larger problem is built from the solutions of smaller subproblems.
            ans[i] = ans[i >> 1] + (i & 1);
        }

        // Return the result array.
        return ans;
    }

    public static void main(String[] args) {
        // Test case 1
        int[] result1 = countBits(2);
        System.out.println(Arrays.toString(result1)); // Expected: [0, 1, 1]

        // Test case 2
        int[] result2 = countBits(5);
        System.out.println(Arrays.toString(result2)); // Expected: [0, 1, 1, 2, 1, 2]
    }
}