Range Queries - print the number of integers in the given range which satisfy the above condition (Easy)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Basic Programming > Bit Manipulation > Basics of Bit Manipulation

Problem

Given $Q$ queries of type $L \ R \ X$, find the count of integers in range $[L, R]$ such that their $X^{th}$ bit (1-indexed) is $ON$ from the LSB (least significant bit) side.

Input Format:

• First line contains an integer $Q$, denoting the number of queries.
• Next $Q$ lines contains three space-separated integres $L \ R \ X$.

Output Format:

For every query, print the number of integers in $[L, R]$ which satisfy the above condition.

Constraints:

$1 \le Q \le 10^5 \\ 1 \le L \le R \le 10^5 \\ 1 \leq X \leq 20$

Sample Input

1
2 6 2

Sample Output

3

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

• Binary representation of integers in range $[2,6]$ are as follows:-
  • 2 : 10
  • 3 : 11
  • 4 : 100
  • 5 : 101
  • 6 : 110
• There are three integers with X-th bit ON i.e. 2, 3 and 6.
• Thus, required answer is 3.

Contributers:

Kritagya Agarwal

Madhumeeta Bauk

---

---

I am learning Data Structures and Algorithms.

I will provide a screenshot of a problem statement. 

Your task is NOT to directly give me the final code solution unless I explicitly ask for it.

Instead, please do the following:

1. First, carefully restate the problem in your own words to confirm correct understanding.
   - If anything is unclear in the screenshot, ask me clarification questions before proceeding.

2. Identify:
   - What category of problem this is (e.g., prefix sum, greedy, DP, two pointers, binary search, graph, etc.)
   - What core DSA concepts are being tested
   - What mathematical observations (if any) are involved
   - What constraints are important and how they affect the approach

3. Explain:
   - What naive/brute-force solution would look like
   - Why that may or may not work under the given constraints
   - What optimization insight is required

4. Clearly explain the key trick or insight needed to solve it.
   - Why does that trick work?
   - What pattern should I remember for future problems?

5. Provide:
   - The time complexity and space complexity of the optimal approach
   - Why it satisfies the constraints

6. If there are multiple valid approaches, compare them.

7. Only after all conceptual explanation, provide clean and correct Python code.

8. Avoid guessing unclear details.
   - If any part of the screenshot is ambiguous, ask me instead of assuming.

Focus on correctness over speed. Be explicit in reasoning.

---

---

Great 👍 Let’s go step by step exactly as you requested.

---

✅ 1. Restating the Problem (Understanding Check)

You are given Q queries.

Each query contains three integers:

Code
L, R, X

For each query, you must count how many integers in the range [L, R] have their X-th bit (1-indexed from the LSB) turned ON.

Important details:

• Bits are counted from the right (LSB).

• X is 1-indexed.

  • X = 1 → check the least significant bit

  • X = 2 → second bit from right

• Constraints:

  • $1 \le Q \le 10^5$

  • $1 \le L \le R \le 10^5$

  • $1 \le X \le 20$

---

Example from screenshot:

Query:

Code
L = 2, R = 6, X = 2

Binary representations:

Number	Binary	2nd bit
2	10	ON
3	11	ON
4	100	OFF
5	101	OFF
6	110	ON

Answer = 3

---

✅ 2. What Type of Problem Is This?

📌 Category:

• Bit manipulation

• Pattern observation

• Prefix counting

• Math-based periodicity

---

📌 Core DSA Concepts Being Tested

• Binary representation

• Understanding bit patterns

• Efficient range counting

• Turning range queries into prefix queries

---

📌 Mathematical Observation

Bits follow a repeating pattern.

For a fixed bit position X:

• That bit repeats every:

  $$2^X$$

• In every cycle of size $2^X$:

  • First $2^{X-1}$ numbers → bit is OFF

  • Next $2^{X-1}$ numbers → bit is ON

So it behaves like:

Code
0000 1111 0000 1111 ...

(for X=3 example)

This periodicity is the key.

---

📌 Constraints Impact

• Q can be 100,000

• R can be up to 100,000

If we do O(R−L) per query, worst case:

$$10^5 \times 10^5 = 10^{10}$$

❌ Impossible.

We need O(1) per query.

---

✅ 3. Naive / Brute Force Approach

For each query:

Code
count = 0
for i in range(L, R+1):
    if (i >> (X-1)) & 1:
        count += 1

Time complexity:

Worst case per query: O(R−L)

Worst case overall: O(Q × N) = 10¹⁰

❌ Too slow.

---

✅ 4. Optimization Insight

Instead of checking each number, we count directly using pattern math.

---

🎯 Core Trick

Define:

$$f(N, X)$$

= number of integers from 1 to N whose X-th bit is ON.

Then answer for range:

$$f(R, X) - f(L-1, X)$$

This converts range query into prefix query.

---

🔎 How to Compute f(N, X)

Let:

$$block = 2^X$$

Each block:

• First half → bit OFF

• Second half → bit ON

Let:

Code
half = 2^(X-1)

Steps:

1. Count full cycles:

   Code
   full_cycles = N // block
   

   Each full cycle contributes:

   Code
   half numbers
   

2. Handle remaining part:

   Code
   remainder = N % block
   

   If remainder < half:
   → contributes 0

   Else:
   → contributes (remainder - half + 1)

So:

$$f(N) = full\_cycles \times half + max(0, remainder - half + 1)$$

---

💡 Why This Works

Because binary bits behave like a square wave:

Code
Length = 2^X
Pattern = [0...0, 1...1]

This repeats forever.

Instead of counting numbers,
we count complete patterns + leftover.

---

🔁 Pattern to Remember for Future

Whenever you see:

• Count numbers in range

• Bit at position X

• Large Q

Think:

Bits follow periodic pattern of size 2^X

And convert:

$$range = prefix(R) - prefix(L-1)$$

This pattern appears in:

• Bit counting problems

• Parity counting

• XOR range problems

• Power-of-two periodic behavior

---

✅ 5. Complexity of Optimal Approach

For each query:

• Only arithmetic operations

• No loops over range

Time Complexity:

$$O(Q)$$

Space Complexity:

$$O(1)$$

This easily satisfies constraints.

---

✅ 6. Multiple Approaches?

Approach 1 (Best): Mathematical periodic counting

Time: O(1) per query
✔ Recommended

---

Approach 2: Precompute prefix arrays for each bit

You could build a 2D array:

Code
prefix[bit][i]

But:

• 20 bits

• N = 10^5

Memory is fine, but unnecessary.

Time complexity:

• Precompute: O(20 × N)

• Query: O(1)

Also valid.

But math approach is cleaner.

---

✅ 7. Clean Python Code (After Full Explanation)

Now here is the implementation:

Python
import sys
input = sys.stdin.read
data = input().split()

q = int(data[0])
index = 1

def count_upto(N, X):
    if N <= 0:
        return 0
    
    block = 1 << X          # 2^X
    half = 1 << (X - 1)     # 2^(X-1)
    
    full_cycles = N // block
    remainder = N % block
    
    count = full_cycles * half
    
    if remainder >= half:
        count += remainder - half + 1
    
    return count

results = []

for _ in range(q):
    L = int(data[index])
    R = int(data[index + 1])
    X = int(data[index + 2])
    index += 3
    
    answer = count_upto(R, X) - count_upto(L - 1, X)
    results.append(str(answer))

print("\n".join(results))

---

If you'd like, next we can:

• Walk through a dry run manually

• Derive the formula visually

• Or convert this to C++ for practice

Your choice 👌