Sudo Placement | Range Queries | CPP program to find the numbers having atmost 3 set bits within a given range ; This function prints the required answer for each query ; Set of Numbers having at most 3 set bits arranged in non - descending order ; 0 set bits ; Iterate over all possible combinations of i , j and k for 60 bits ; 1 set bit ; 2 set bits ; 3 set bits ; Answer Queries by applying binary search ; Swap both the numbers if L is greater than R ; Driver Code ; Number of Queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define LL  long long int NEW_LINE void answerQueries ( LL Q , vector < pair < LL , LL > > query ) { set < LL > s ; s . insert ( 0 ) ; for ( int i = 0 ; i <= 60 ; i ++ ) { for ( int j = i ; j <= 60 ; j ++ ) { for ( int k = j ; k <= 60 ; k ++ ) { if ( j == i && i == k ) s . insert ( 1LL << i ) ; else if ( j == k && i != j ) { LL x = ( 1LL << i ) + ( 1LL << j ) ; s . insert ( x ) ; } else if ( i == j && i != k ) { LL x = ( 1LL << i ) + ( 1LL << k ) ; s . insert ( x ) ; } else if ( i == k && i != j ) { LL x = ( 1LL << k ) + ( 1LL << j ) ; s . insert ( x ) ; } else { LL x = ( 1LL << i ) + ( 1LL << j ) + ( 1LL << k ) ; s . insert ( x ) ; } } } } vector < LL > validNumbers ; for ( auto val : s ) validNumbers . push_back ( val ) ; for ( int i = 0 ; i < Q ; i ++ ) { LL L = query [ i ] . first ; LL R = query [ i ] . second ; if ( R < L ) swap ( L , R ) ; if ( L == 0 ) cout << ( upper_bound ( validNumbers . begin ( ) , validNumbers . end ( ) , R ) - validNumbers . begin ( ) ) << endl ; else cout << ( upper_bound ( validNumbers . begin ( ) , validNumbers . end ( ) , R ) - upper_bound ( validNumbers . begin ( ) , validNumbers . end ( ) , L - 1 ) ) << endl ; } } int main ( ) { int Q = 2 ; vector < pair < LL , LL > > query ( Q ) ; query [ 0 ] . first = 3 ; query [ 0 ] . second = 7 ; query [ 1 ] . first = 10 ; query [ 1 ] . second = 16 ; answerQueries ( Q , query ) ; return 0 ; }