Skip to main content
Talentd

Count Monobit Integers - Solution & Explanation

EasyBit ManipulationEnumeration5 min readAsked at: Zoho
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Count how many integers in the given range are monobit. A monobit integer has exactly one set bit (1) in its binary representation. In other words, its binary form looks like 1, 10, 100, 1000, etc.

Approach 1: Simulation with Bit Check (O(n) time, O(1) space)

The straightforward approach is to iterate through every integer in the range and check whether it contains exactly one set bit. A number has a single set bit if the expression x & (x - 1) equals zero while x > 0. This works because subtracting 1 flips the lowest set bit and all bits to its right, so the bitwise AND removes that bit entirely for powers of two.

During the scan, perform this constant‑time check for each number and increment a counter whenever the condition holds. This technique relies on a classic Bit Manipulation trick that quickly detects whether a number is a power of two. Since each integer is processed once, the runtime is linear with respect to the size of the range.

This method is simple, readable, and efficient for the typical constraints of an easy problem. The logic involves basic Enumeration: iterate through candidates and validate them using a constant‑time property of their binary form.

Why the bit trick works: Numbers with exactly one set bit are powers of two. Their binary representation contains a single 1. When you compute x & (x - 1), that single bit disappears, producing zero. Any number with multiple set bits leaves at least one bit after the operation.

Recommended for interviews: The simulation approach using x & (x - 1) is what interviewers typically expect. It shows familiarity with core bit manipulation patterns. A brute-force method that counts bits using loops also works, but the bit trick demonstrates stronger understanding and runs with the same O(n) time while keeping the code concise.

Solution

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

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

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Count per NumberO(n log n)O(1)Simple brute force when checking bits by shifting or built-in popcount
Bit Trick: x & (x - 1)O(n)O(1)Best general solution; constant-time monobit check using bit manipulation

Video Solution

Count Monobit Integers | Leetcode 3827 | Weekly Contest 487 | Java Code | Developer Coder • Developer Coder • 363 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Count Monobit Integers easy or hard?
Count Monobit Integers is considered an easy problem. The core idea is recognizing that numbers with exactly one set bit are powers of two and can be detected using a standard bit manipulation trick.
Count Monobit Integers Python/Java solution
The implementation in Python, Java, C++, Go, or TypeScript follows the same logic: loop through numbers and check if x & (x - 1) == 0. If true, increment a counter. The code stays short and runs in O(n) time with constant memory.
How to solve Count Monobit Integers in O(n)?
Iterate through every integer in the range and apply the bit trick x & (x - 1). If the result equals zero and the number is positive, it contains exactly one set bit. Count all numbers satisfying this condition to obtain the result in linear time.
What is the best approach for Count Monobit Integers?
The most efficient approach iterates through the numbers and checks whether each value has exactly one set bit using the expression x & (x - 1) == 0. This works because only powers of two satisfy this property. The algorithm runs in O(n) time with O(1) extra space.
Is Count Monobit Integers asked at Google/Amazon/Meta?
Bit manipulation questions involving power-of-two checks and set-bit properties frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem are commonly used to test understanding of binary operations and bit tricks.
What data structure is used in Count Monobit Integers?
No complex data structure is required. The solution relies on bitwise operations and simple iteration. The key concept comes from bit manipulation rather than arrays, trees, or hash maps.
What is the time complexity of Count Monobit Integers?
The optimal solution runs in O(n) time where n is the number of integers examined in the range. Each integer is checked once using a constant-time bit manipulation operation. Space complexity remains O(1) because only a counter variable is required.

Ready to solve this problem?

Practice Count Monobit Integers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary