whats wrong with my solution for Xor and xnor (4th problem)

solution link

solution start after the template

I am also getting wrong answer.

#include

#include<bits/stdc++.h>

using namespace std;

int main() {

// your code goes here

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;

}

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]=='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]=='0') return 0;
//if(num.back()=='0') return 0;
vector<vector<ll>> dp(2,vector<ll>(num.size()));
dp[0][0]=1;
dp[1][0]=0;
for(int i=1;i<(ll)num.size();i++){
dp[0][i]=num[i]!='0'?((dp[0][i-1])%M+(dp[1][i-1])%M)%M:0;
dp[1][i]=((num[i-1]=='1' or (num[i-1]=='2' and num[i]<='6')) and num[i-1]!=0)?dp[0][i-1]:0;
}
//vdeb(dp[0],dp[1]);
return (dp[0][num.size()-1]+dp[1][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.

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