A XOR problem - HackerEarth Solution
A XOR problem - HackerEarth Solution
You are given two positive integers \(X\) and \(Y\) without leading zeroes. You can perform an operation on these integers any number of times, in which you can delete a digit of the given number such that resulting number does not have leading zeroes. Let \(X'\) and \(Y'\) be two numbers that were formed after performing operations on \(X\) and \(Y\) respectively.
You have to find all the unique pairs of \(X'\) and \(Y'\) whose XOR is zero.
Note: Two pairs of numbers \((A, B)\) and \((C, D)\) are considered different if and only if \(A!=C\) or \(B!=D\) .
Input format
- First line: An integer \(T\) denoting the number of test cases
- Each of the next \(T\) lines: Two space-separated integers \(X\) and \(Y\)
Output format
- For each test case, print the answer in a new line.
Constraints
\(1 \le T \le 10 \\ 1 \le X, Y \le 10^{12} \\\)
Sample Input
2 12 102 13 33
Sample Output
3 1
Sample Explanation
For the test case 1,
- Possible values of X' are [1,2,12]
- Possible values of Y' are [1,2,10,12,102]
So, three pairs (1,1), (2,2), (12,12) have xor zero.
For the test case 2,
- Possible values of X' are [1,3,13]
- Possible values of Y' are [3,33] (We can generate 3 two times)
So, one unique pair (3,3) has xor zero.
A XOR problem - HackerEarth Solution
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int main()
{
//freopen("in1.txt","r",stdin);
//freopen("out1.txt","w",stdout);
int t;
cin>>t;
while(t--){
LL x,y;
cin>>x>>y;
string X,Y;
X = to_string(x);
Y = to_string(y);
unordered_map<LL,LL> um;
for(int i=0;i<(1<<X.length());i++)
{
LL num = 0;
for(int j=0;j<X.length();j++)
{
if(i&(1<<j))
{
num = num*10 + (X[j]-'0');
}
}
if(num!=0)
{
um[num]++;
}
}
set<LL> st;
for(int i=0;i<(1<<Y.length());i++)
{
LL num = 0;
for(int j=0;j<Y.length();j++)
{
if(i&(1<<j))
{
num = num*10 + (Y[j]-'0');
}
}
st.insert(num);
}
LL ans=0;
for(auto k:st)
{
if(um[k])
{
ans++;
}
}
cout<<ans<<"\n";}
return 0;
}
Post a Comment