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: XNOR of two numbers - GeeksforGeeks
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.