Range Queries

4.5

2 votes
Bit Manipulation, Basics of Bit Manipulation, Basic Programming
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\)

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.
Editor Image

?