What is the time complexity of the Brute Force Enumeration approach?

The time complexity is O(n log n), as we iterate through n numbers and perform bitwise operations.

What is the time complexity of the Mathematical Bit Length approach?

The time complexity is O(1), as it involves a single arithmetic or bit operation.

What is the time complexity of the Iterative Bit Generation approach?

The time complexity is O(log n), as we iterate through the number of bits in n.

Count Monobit Integers

Difficulty: Easy | Acceptance: 66.40% | Paid: No Topics: Bit Manipulation, Enumeration

An integer is monobit if its binary representation consists of only 0s or only 1s.

Given an integer n, return the count of monobit integers in the range [0, n].

Examples
Constraints
Approach 1: Brute Force Enumeration
Approach 2: Mathematical Bit Length
Approach 3: Iterative Bit Generation

Examples

Example 1

Input:

n = 1

Output:

Explanation: The integers in the range [0, 1] have binary representations “0” and “1”.

Each representation consists of identical bits. Thus, the answer is 2.

Example 2

Input:

n = 4

Output:

Explanation: The integers in the range [0, 4] include binaries “0”, “1”, “10”, “11”, and “100”.

Only 0, 1 and 3 satisfy the Monobit condition. Thus, the answer is 3.

Constraints

- 0 <= n <= 1000

Approach 1: Brute Force Enumeration

Intuition Iterate through every number from 0 to n and check if its binary representation contains only 0s or only 1s.

Steps

Initialize a counter to 0.
Loop through each integer i from 0 to n.
For each i, check if it is 0 (all 0s) or if i & (i + 1) == 0 (all 1s).
If the condition is met, increment the counter.
Return the counter.

python

class Solution:
    def countMonobitIntegers(self, n: int) -&gt; int:
        count = 0
        for i in range(n + 1):
            if i == 0:
                count += 1
            elif (i & (i + 1)) == 0:
                count += 1
        return count

Complexity

Time: O(n log n)
Space: O(1)
Notes: This approach is too slow for the upper constraint of n = 10⁹.

Approach 2: Mathematical Bit Length

Intuition A monobit integer is either 0 or a number of the form 2ᵏ - 1 (e.g., 1, 3, 7, 15…). The count of such numbers up to n is equivalent to the number of bits required to represent n + 1.

Steps

Calculate n + 1.
Return the bit length of n + 1. In most languages, this is a built-in operation or can be derived from the binary string length.

python

class Solution:
    def countMonobitIntegers(self, n: int) -&gt; int:
        return (n + 1).bit_length()

Complexity

Time: O(1)
Space: O(1)
Notes: This is the optimal solution, leveraging mathematical properties of binary numbers.

Approach 3: Iterative Bit Generation

Intuition Generate all numbers of the form 2ᵏ - 1 that are less than or equal to n, and count them along with 0.

Steps

Initialize count = 1 (for 0) and val = 1.
While val - 1 <= n, increment count and multiply val by 2.
Return count.

python

class Solution:
    def countMonobitIntegers(self, n: int) -&gt; int:
        count = 1
        val = 1
        while val - 1 &lt;= n:
            count += 1
            val *= 2
        return count

Complexity

Time: O(log n)
Space: O(1)
Notes: Efficient enough for constraints, but slightly slower than the direct bit length calculation.