 # CODEFISTA xor problem

whats wrong with my solution for Xor and xnor (4th problem)
solution start after the template

I am also getting wrong answer.
#include
#include<bits/stdc++.h>
using namespace std;
int main() {
long long ans,n,t,i,a,b,nx,nxn,na,nb;
cin>>t;
while(t–)
{
cin>>a>>b>>n;
na=a;
nb=b;
if(n==2)
ans=b;
else
{
for(i=3;i<=n;i++)
{
nx=a^b;
a=b;
b=nx;
nxn=!(na^nb);
na=nb;
nb=nxn;
}
ans=max(nx,nxn);
}
cout<<ans<<endl;
}
return 0;
}

2 Likes

Please Look at the cheater from the contest who topped this contest

I am getting TLE also and my code T.C is O(n).

O(n) won’t work here.
Use this XOR property : A, B, C form a XOR Triangle,
where A XOR B = C , B XOR C = A, A XOR C = B.
Same will follow for XNOR with a exception for A XNOR B = 0 case.

Check out my submission : Solution for XOR-XNOR

``````#include <bits/stdc++.h>
#define MOD 1000000007;
using namespace std;

int countDecoding(string digits, int n)
{
if (n == 0 || n == 1)
return 1;
if (digits=='0')
return 0;

int count = 0;

if (digits[n-1] > '0')
count = countDecoding(digits, n-1) % MOD;

if (digits[n-2] == '1' ||
(digits[n-2] == '2' && digits[n-1] < '7') )
count += countDecoding(digits, n-2) % MOD;

return count % MOD;
}

int main()
{
int tt;
cin >> tt;
while(tt--){
string str;
cin >> str;
int n = str.length();
cout << countDecoding(str, n) << endl;
}
return 0;
}
``````

What’s wrong with this one?

I think you have got an overflow problem you are calculating the number of bits in the XOR value, right so suppose the number is a huge number whose bit representation is around 50-60 bits long, so when you will calculate:

This

for(int i=0;i<bits(ans);i++)
{
ans1+=((1<<i)&ans)?0:pow(2,i);
}

The power function will definitely cause an overflow for larger numbers, either try to write your own power function using Binary Exponentiation or instead of that:

Try this

You can calculate XNOR in 0(1) time too: https://www.geeksforgeeks.org/xnor-two-numbers/

Recursion . DP is the way out

''ll solve(){

``````string num;
cin>>num;

if(num=='0') return 0;
//if(num.back()=='0') return 0;

vector<vector<ll>> dp(2,vector<ll>(num.size()));

dp=1;
dp=0;
for(int i=1;i<(ll)num.size();i++){
dp[i]=num[i]!='0'?((dp[i-1])%M+(dp[i-1])%M)%M:0;
dp[i]=((num[i-1]=='1' or (num[i-1]=='2' and num[i]<='6')) and num[i-1]!=0)?dp[i-1]:0;
}

//vdeb(dp,dp);
return (dp[num.size()-1]+dp[num.size()-1])%M;
``````

}’’

why my code is giving TLE for the last DP problem

Xnor is not at all this-> nxn=!(na^nb) ; this is logical not …
& also for(i=3;i<=n;i++) -> this will lead to TLE .
the XOR triplet is always same a , b , a^b .
only XNOR will vary but after a certiain time which is multiple of 3 the XNOR triplet will aslo become same but any way the for first time XNOR(a,b) >=<XOR(a,b) but after that XOR is always greater…

the problem would beome good if instead of max , min value would ask.

size of n is too big 10^12

I can’t see why min value question would be harder. There’s a clear pattern here

i’m not saying harder , i’m saying good if that would be…

Thank you for sharing the correct approach and logic i was confused after reading the top submissions but now it is clear.

1 Like

@zappelectro Will u please tell me why in line 80,u are printing max of e & b.

We need to print max(XOR,XNOR) values as mentioned in the problem statement.

1 Like