LeetCode Notes: Counting Bits

#leetcode

Question

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of1's in the binary representation of i.

Example 1:

Input: n = 2

Output: [0,1,1]

Explanation:

0 --> 0

1 --> 1

2 --> 10

Example 2:

Input: n = 5

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

Explanation:

0 --> 0

1 --> 1

2 --> 10

3 --> 11

4 --> 100

5 --> 101

Constraints:

  • 0 <= n <= 105

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
  • Could you solve it in O(n) space complexity?
  • Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution One

Analysis:

Get each number in a loop, convert it to binary, use regular expressions to find out how many numbers 1 in it, and then store it in the result array

Code:

/**
  * @param {number} n
  * @return {number[]}
  */
var countBits = function(n) {
     // Store the result
     const result = [];

     // loop to get each number
     for(let i = 0; i <= n; i++){
         // Core method: Convert decimal numbers to binary, and match the number of digits 1
         const matchOne = (i).toString(2).match(/1/g)
         // If we get an array of matching values, we return the number of matches, otherwise we return 0 directly
         result.push(matchOne? matchOne.length: 0)
     }

     // return result
     return result
};

Solution Two

Analysis:

To upgrade to the first solution, use the map method on the newly created array to quickly get an array, and the internal processing of the function is still the same as above

Code:

/**
  * @param {number} n
  * @return {number[]}
  */
var countBits = function(n) {
     // Create an array of n+1 length and traverse the array
     return new Array(n+1).fill(0).map((item,i)=>{
         // The number of regular matches 1
         const matchOne = (i).toString(2).match(/1/g)
         return matchOne? matchOne.length: 0
     })
};

Reference

Comments