This is the sixth day of my participation in Gwen Challenge

The original problem

Bit count

Given a non-negative integer num. For each number I in the range 0 ≤ I ≤ num, count the number of 1s in its binary number and return them as an array.

  • An operation
  • Dynamic programming

Example 1:

Input: 2 output: [0,1,1]Copy the code

The sample? 2:

Input: 5 Output: [0,1,1,2, 2]Copy the code

Advanced:

  • It is very easy to give a solution with time complexity of **O(n*sizeof(INTEGER)). But can you do that in one scan in linear time O(n)**?
  • The space complexity of the algorithm is O(n).
  • Can you refine the solution further? Requires that you do this without using any built-in functions (such as __builtin_popcount in C++) in C++ or any other language.

jolt

I couldn’t figure out why it was dynamic programming at first, and then I started scribbling, writing binary representations of each number, and then I seemed to find something. (The simple question is really difficult)

List the binary representations of 0-9:

0 = 0 0 0 1 = 0 0 1 2 = 0 0 1 0 3 = 0 0 1 1 4 = 0 1 0 0 5 = 0 1 0 1 6 = 0 1 1 0 7 = 0 1 1 1 1 8 = 1 0 0 9 = 1 0 0 1Copy the code

Look at these things up here, because if you want to use dynamic programming, you have to figure out their recursion. First we can find:

  • If it’s even

    For example, 2, 4, 6 their binary representation is related to their 1/2. For example, the binary representation of 2 is 1 << 1 moved one bit to the left, and 4 is 2 << 1, and 6 is 3 << 1. After all, we’re multiplying by 2

  • If it’s an odd number

    Suppose this number is n, then its binary representation is the binary representation of n-1 with a 1 added to the end; And we can do it the other way around, because the binary end of an odd number is 1, so if you take the 1 out of the binary end of an odd number it’s equal to the binary representation of n minus 1. And n minus 1 is even, so we can use the even case, so the number of binary 1’s in odd number n is equal to the number of binary 1’s in n over 2 plus 1.

  • subproblems

    The above two cases can be recurred, so we can set the subproblem so that dp[n] is the number of ones in the binary number of n

  • equation

    Based on the initial reasoning, it is relatively easy to write the following state transition equation (starting from 0) :


    d p ( n ) = { 0   n = 0 d p [ n ] = d p [ n > > 1 ] + ( n & 1 )   n > 1 dp(n)=\left\{ \begin{aligned} 0 & &\ n = 0 \\ dp[n] = dp[n >> 1] + (n \& 1) & &\ n > 1 \\ \end{aligned} \right.

  • Write code that combines conditions

        public int[] countBits(int n) {
        // Initialize the dp array
        int[] dp = new int[n+1];
        // The code is derived from the equation
        for (int i = 1; i < n + 1; i++) {
            // I & 1 is the unique number at the end, which can be used as a parity case
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
Copy the code

closed

  • To find a subproblem for a dynamic specification problem, you need to find a recursive relationship first (actually you can write a recursive solution then).