This post is completed by 1 user

  • 0
 Add to List
Beginner

554. Counting bits - Leetcode

Problem Statement:

You are given a non-negative integer n. Your task is to generate an array ans of size n + 1 where each element ans[i] represents the number of 1s in the binary representation of the integer i, for i ranging from 0 to n (inclusive).

Examples:

  • Example 1:

    • Input: n = 2
    • Output: [0, 1, 1]
    • Explanation:
      • The binary representation of 0 is 0, which contains 0 ones.
      • The binary representation of 1 is 1, which contains 1 one.
      • The binary representation of 2 is 10, which contains 1 one.

  • Example 2:

    • Input: n = 5
    • Output: [0, 1, 1, 2, 1, 2]
    • Explanation:
      • The binary representations are as follows:
        • 0 is 0, with 0 ones.
        • 1 is 1, with 1 one.
        • 2 is 10, with 1 one.
        • 3 is 11, with 2 ones.
        • 4 is 100, with 1 one.
        • 5 is 101, with 2 ones.

Constraints:

  • 0 <= n <= 100,000

Solution

The brute-force solution to counting the number of 1s in the binary representation of integers. For each number from 0 to n, the solution calculates the number of 1s by repeatedly checking the least significant bit and then shifting the number to the right. This bitwise operation is performed for every number in the range

Time Complexity: O(nlog⁡n)

 

Output:

[0, 1, 1, 2, 1, 2]

[0, 1, 1, 2, 1, 2, 2, 3]

Better Solution:

To efficiently count the number of 1s in the binary representation of integers from 0 to n, we can leverage the properties of binary numbers, specifically focusing on whether a number is even or odd:

Even Numbers

In binary, even numbers end with a 0. This means the number of 1s in the binary representation of an even number is the same as the number of 1s in the binary representation of the number right-shifted by one bit. Mathematically, for an even number num, we have:

countBits(num) = countBits(num >> 1)

For example:

num = 101010101010 (binary), right-shifting gives num >> 1 = 10101010101, and the number of 1s remains unchanged.

Odd Numbers

Odd numbers end with a 1 in binary. To count the 1s in such numbers, we add one to the count of 1s of the number that is one less than the given number. Thus:

countBits(num) = countBits(num - 1) + 1

For example:

num = 101010101011 (binary), num - 1 = 101010101010. The count of 1s is one more than that of num - 1.

Time Complexity: O(n)

 

Output:

[0, 1, 1, 2, 1, 2]

[0, 1, 1, 2, 1, 2, 2, 3]

Reference- Leetcode

Related Problems: