Problem name :- ORTUPLES Problem - CodeChef
Problem statement :- Chef has 3 numbers P, Q and R. Chef wants to find the number of triples (A,B,C) such that:
- (A∣B)=P,(B∣C)=Q and (C∣A)=R
- 0 <= A,B,C < pow(2,20)
Can you help Chef?
Input Format :-
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of a single line of input containing 3 space-separated integers denoting
P,Q and R respectively.
Output Format :-
For each test case, output a single integer denoting the number of triplets (A,B,C) that satisfy the given conditions.
Constraints :-
1 ≤ T ≤ pow(10,5)
0 ≤ P, Q, R < pow(2,20)
Logic :- I am checking individual bits of p, q and r; whenever i am getting something like 100, 010 or 001 i am printing 0 (i.e. no solution possible) and otherwise if there is some bit common in all three p,q and r then for each such bit 4 combinations are possible so answer would be pow(4,common_bits).
Implementation :-
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int p, q, r;
cin >> p >> q >> r;
int common = (p & q & r);
int countSetBits = __builtin_popcount(common);
int trkr = 1;
while(p || q || r){
if((p>>1) + (q>>1) + (r>>1) == 1){
trkr = 0;
break;
}
p >>= 1;
q >>= 1;
r >>= 1;
}
if(trkr){
if(countSetBits > 0)
cout << (1 << (2*countSetBits)) << endl;
else
cout << 1 << endl;
} else {
cout << 0 << endl;
}
}
int32_t main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Issue :- But its giving wrong answer, so someone can please help me to find out where am I going wrong, is my logic wrong or the implementation part wrong?