InMobi Interview QuestionSenior Software Development Engineers
- 0of 0 votes
A special number is defined as a number where, in binary notation,
a. has only set bits (OR)
b. all set bits are followed by unset bits (OR)
c. the sequence formed by count of the number of set bits separated by any number of unset bits is a contiguous subsequence of the sequence of natural numbers.
2, 3, 11271 and 15667135 are special numbers because their binary represenation is 10, 11, 10110000000111 and 111011110000111110111111 respectively.
2 is a special number because of condition (b).
3 is a special number because of condition (a).
11271 is a special number because its binary representation is 10110000000111 because of condition (c). The sequence of the count of number of set bits separated by a unset bits is 1, 2 and 3. This is clearly a continguous subsequence of the natural numbers.
Similarly, 15667135 is a special number. (The sequence is 3,4, 5 and 6.)
So, given two integers n and m where n <= m, find out the number of special numbers between n and m inclusive.
The first line of input contains an integer T where T is the number of test cases. Then T lines follow containing two space separated integers n and m where n <= m.
For each test case, output, in different lines, a single integer P where P is the number of special numbers between the range specified.
1 <= T <= 1000
1 <= n <= 10^6
1 <= m <= 10^6
n <= m
Interview Type: Written Test