I am using recursive approach , but failed to further optimize it. It is getting passed for subtask , how to improve the efficiency:
#include <bits/stdc++.h>
using namespace std;
void func(long JS,long TS,long &count){
if(JS<1 || ( (JS&1) && (TS&1)))
return;
if((TS&1) && !(JS&1)){
count++;
}
if(!(TS&1) && !(JS&1)){
func(JS>>1,TS>>1,count);
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
long TS,ans=0;
cin>>TS;
for(long i=1;i<=TS;i++){
long c=0;
func(i,TS,c);
ans+=c;
}
cout<<ans<<endl;
}
return 0;
}