# PROBLEM LINK:

https://www.codechef.com/START24C/problems/ORANDCON

Setter: Utkarsh Gupta
Tester: Aryan Chaudhary
Editorialist: Rishabh Gupta

Simple

None

# PROBLEM:

You are given a positive integer X which is at most 10^8.

Find three distinct non-negative integers A,B,CA,B,C that do not exceed 10^9 and satisfy the following equation:

( A | B ) \& ( B | C ) \& ( C | A) = X

Here, | denotes the bitwise OR operator and & denotes the bitwise AND operator.

It can be shown that a solution always exists for inputs satisfying the given constraints. If there are multiple solutions, you may print any of them.

# EXPLANATION:

Every set bit of X must be present in (A|B), (B|C) and (A|C) which also boils down to the fact that every set bit of X must be present in at least 2 of A,B and C.
So, we can make a construction as A = X = B, C= 0. To make A!=B we can add a larger power of 2 to A(say 2^{27}), making sure it does not get larger than 10^9.

# TIME COMPLEXITY:

O(1) for each test case.

# SOLUTION:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
LL seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)
clock_t start = clock();

#define getchar getchar_unlocked

namespace IO {
long long readInt(char endd) {
long long ret = 0;
char c = getchar();
while (c != endd) {
ret = (ret * 10) + c - '0';
c = getchar();
}
return ret;
}
long long readInt(long long L, long long R, char endd) {
long long ret = readInt(endd);
assert(ret >= L && ret <= R);
return ret;
}
long long readIntSp(long long L, long long R) {
return readInt(L, R, ' ');
}
long long readIntLn(long long L, long long R) {
return readInt(L, R, '\n');
}
string readString(int l, int r) {
string ret = "";
char c = getchar();
while (c == '0' || c == '?' || c == '1') {
ret += c;
c = getchar();
}
assert((int)ret.size() >= l && (int)ret.size() <= r);
return ret;
}
}
using namespace IO;

const int TMAX = 100;

void solve() {
int x = readIntLn(1, (int)1e8);
int pos = 0, ret[3] = {0};
for (int j=26;j>=0;--j) {
for (int k=0;k<3;++k) {
ret[k] |= (((pos == k) ^ ((x >> j) & 1)) << j);
}
pos = (pos == 2 ? 0 : pos + 1);
}
cout << ret[0] << " " << ret[1] << " " << ret[2] << '\n';
assert(((ret[0] | ret[1]) & (ret[1] | ret[2]) & (ret[2] | ret[0])) == x);
}

int main() {
int T = readIntLn(1, TMAX);
while (T--) {
solve();
}
// assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << " secs\n";
return 0;
}
``````
Editorialist''s Solution
``````#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef NOOBxCODER
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#define NOOBxCODER 0
#endif
cin>>t;
//t=1;
while(t--){
int a;
cin>>a;
cout<<a<<" "<<a + (1<<27)<<" "<< 0<<endl;

}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}

``````
4 Likes

Why my code is not passing all test cases?
#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(tβ){
int x;
cin>>x;
if(x&1)
cout<<x<<" β<<x-1<<β β<<x-2;
else
cout<<x<<β β<<x+1<<β "<<x+2;
cout<<endl;
}

``````return 0;
``````

}

2 Likes

check for x=1

3 Likes

think about x = 1

1 Like

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define For(a, c) for (int(a) = 0; (a) < (c); (a)++)

#define FORL(a, b, c) for (long long int(a) = (b); (a) <= (c); (a)++)

#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); (a)β)

#define mp make_pair

#define pb push_back

#define Pob pop_back

#define F first

#define S second

typedef vector vll;

typedef vector vi;

typedef vector<vector> vii;

typedef pair<int, int> pi;

bool isPowerOfTwo(int n)

{

if(n==0)

return false;

return (ceil(log2(n)) == floor(log2(n)));

}

int main(){

ios::sync_with_stdio(0);

cin.tie(NULL);

cout.tie(NULL);

int t;

cin >> t;

while(tβ){

``````ll x;

cin >> x;

if(isPowerOfTwo(x)){

cout<<x<<" "<<x+1<<" "<<x+2<<"\n";

}

else if(x % 10 == 0 || x%2 == 0) {

for(ll i=2; i<x; i*=2){

ll ele = ((i|x-1) & (x-1|x) & (x|i));

if(ele == x) cout<<i<<" "<<x-1<<" "<<x<<"\n";

}

}

else{

cout<<"1"<<" "<<x-1<<" "<<x<<"\n";

}
``````

}

return 0;

}

On which tc my code will not run, can somebody tell me.?

Hello can anybody help me figure out how this code was AC for only 1 hidden test case??

#include
#include<bits/stdc++.h>
using namespace std;

int getbit(int n){
int check=1;
while ((n&check)==0)
{
check= check<<1;
}

``````return check;
}
``````

bool isPowerOfTwo(int n)
{
if(n==0)
return false;

return (ceil(log2(n)) == floor(log2(n)));
}

int main(int argc, char const *argv[])
{
int tc;
cin>>tc;

``````while (tc--)
{
int x;
cin>>x;

if (isPowerOfTwo(x))
{
cout<<x<<" "<<x+1<<" "<<x+2<<endl;
}
else
{
int j=getbit(x);
cout<<j<<" "<<x-j<<" "<<x<<endl;
}

}

return 0;
``````

}

can somebody tell where i am getting wrong in this code

#include <bits/stdc++.h>
using namespace std;

void solve()
{
int x;
cin>>x;
int arr[3]={0,0,0};
arr[0]=x;
int temp=0,counter_z=0;
int bits = log2(x)+1;

``````int maxi = max(bits,3);
if((x&(x-1))==0){
for(int i=0;i<maxi;i++)
{
temp=pow(2,i);
if((x&temp))
{
for(int j=0;j<3;j++)
{
if(j!=counter_z)
{
arr[j] += pow(2,i);
}
}

}
else
{
for(int j=0;j<3;j++)
{
if(j==counter_z)
{
arr[j] += pow(2,i);
}
}

}
counter_z++;
}
``````

}
else{
for(int i=0;i<bits;i++)
{
temp=pow(2,i);
if((x&temp))
{ if(counter_z==1)
{
arr[2]+=pow(2,i);
}

``````    		else arr[1]+=pow(2,i);
counter_z++;

}

}
``````

}
for(int j=0;j<3;j++) cout<<arr[j]<<" β;
cout<<β\n";
// int a=arr[0],b= arr[1],c= arr[2];
// cout<<((a|b)&(b|c)&(c|a));
// cout<<endl;
}
int main() {
int test;
cin>>test;
while(testβ)solve();
// your code goes here
return 0;
}

check for x= 1

correct for 1. For 1, (1,2,3) is my output

#include <bits/stdc++.h>

using namespace std;

int main(){

``````int t;

cin>>t;

while(t--){

long long X;

cin>>X;

if(X==1){

cout<<"1"<<"   "<<"2"<<"   "<<"7"<<endl;

}

else if(X%2==0){

cout<<X<<"   "<<X+1<<"   "<<X+2<<endl;

}

else{

cout<<X-2<<"   "<<X-1<<"   "<<X<<endl;

}

}
``````

}

why is it not accepting the solutionβ¦ i have taken care of X=1 tooβ¦ give me some examplesβ¦

1 Like

for x = 1 the last one is going to be negative number which we donβt want so for x == 1 print directly 0 1 3 or any other case if there for 1

even i also thought the same thing but got WA

can anyone tell me my mistake??

#include<bits/stdc++.h>

using namespace std;

int main(){

int T;

cin>>T;

while(Tβ){

long long n;

cin>>n;

if(n==1)

cout<<β1β<<" β<<β2β<<β "<<β7β<<endl;

else if(n%2==0)

cout<<n<<" β<<n+1<<β "<<n+2<<endl;

else

cout<<n-2<<" β<<n-1<<β "<<n<<endl;

}

return 0;

}

This is Correct ansβ¦
#include<bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(tβ){
int x;
cin>>x;
if(x==1)
cout<<3<<" β<<1<<β β<<0;
else if(x&1)
cout<<x<<β β<<x-1<<β β<<x-2;
else
cout<<x<<β β<<x+1<<β "<<x+2;
cout<<endl;
}

``````return 0;
``````

}

1 Like

Think for x = 1
Your Output : 1 2 3

But when you calculate : (1|2) & (2|3) & (3|1)
it gives you 3 not 1

``````#include <bits/stdc++.h>
using namespace std;
void solve()
{

long long x;
cin>>x;
if(x%2)
{
if(x==1)
{
cout<<"1"<<" 2"<<" 4\n";
return;
}
cout<<"1"<<" "<<x-1<<" "<<x<<endl;
}
else
{
if(x==2)
{
cout<<"1 6 2\n";
return;
}
cout<<2<<" "<<x+1<<" "<<x<<endl;
}

}

int main() {
int test;
cin>>test;
while(test--)
solve();
return 0;
}

``````

Please anyone give hidden testcase which fails this code.

For X = 1, it will fail. For X = 1, your answer will be 1, 0 and -1 but in the constraint negative numbers are not allowed. So take it as base case and try to find any three numbers that satisfy for X = 1.

I probably got the same issue but i figured it out.

for x = 1 , your output is wrong.

when you calculate : (1|2) & (2|4) & (4|1)
it gives you 0 not 1

heyy please can you tell me for which number I am getting wrong answer

#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin>>t;
while(tβ){

``````    long long int n;
cin>>n;
if(n!=1){
cout<<0<<" ";
cout<<n<<" ";
long long int x=ceil(log2(n));
cout<<pow(2,x)-1<<endl;
}
if(n==1){
cout<<0<<" ";
cout<<1<<" "<<1<<endl;
}
}

return 0;
``````

}