CODEFISTA xor problem

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;
}

@admin please add all problems to practice section

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]=='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: XNOR of two numbers - GeeksforGeeks

Recursion :frowning:. 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.

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