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

1Q1051LR1051X20

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

?