Skip to content

3827. Count Monobit Integers

Description

You are given an integer n.

An integer is called Monobit if all bits in its binary representation are the same.

Return the count of Monobit integers in the range [0, n] (inclusive).

 

Example 1:

Input: n = 1

Output: 2

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: 3

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

Solutions

Solution 1: Simulation

Thinking

A monobit integer has all bits equal: \(0\) or a number of the form \(2^{t}-1\). \(n \le 1000\) allows scanning \([0,n]\), but it is enough to generate these values.

Start from \(1\) and repeatedly add the next higher \(1\)-bit, producing \(1,3,7,\ldots\) until the value exceeds \(n\).

Counting \(0\) as well gives the size of the range.

The loop runs \(O(\log n)\) times.

According to the problem description, a Monobit integer is either \(0\), or its binary representation consists of all \(1\)s.

Therefore, we first include \(0\) in the answer, then starting from \(1\), we sequentially generate integers whose binary representations consist of all \(1\)s, until the integer exceeds \(n\).

The time complexity is \(O(\log n)\) and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def countMonobit(self, n: int) -> int:
        ans = x = 1
        i = 1
        while x <= n:
            ans += 1
            x += 1 << i
            i += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int countMonobit(int n) {
        int ans = 1;
        for (int i = 1, x = 1; x <= n; ++i) {
            ++ans;
            x += (1 << i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int countMonobit(int n) {
        int ans = 1;
        for (int i = 1, x = 1; x <= n; ++i) {
            ++ans;
            x += (1 << i);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func countMonobit(n int) (ans int) {
    ans = 1
    for i, x := 1, 1; x <= n; i++ {
        ans++
        x += (1 << i)
    }
    return
}

1
2
3
4
5
6
7
8
function countMonobit(n: number): number {
    let ans = 1;
    for (let i = 1, x = 1; x <= n; ++i) {
        ++ans;
        x += 1 << i;
    }
    return ans;
}

Comments