In this HackerEarth XORing in Base 10 problem solution we have given two numbers A = (A0A1…An) and B = (B0B1…Bn) in base 10, we define the xor of A and B as A . B = (X0X1…Xn), where Xi = (Ai + Bi) mod 10.
Little Achraf has an array S of integers in base 10 and he was asked by his professor Toman to find the maximum number he can get by XORing exactly k numbers.
HackerEarth Xoring in Base 10 problem solution.
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int max_len = 10;
const int max_nodes = 5000000;
struct node {
int nxt[10];
node() {
memset(nxt, -1, sizeof(nxt));
}
};
int next_free;
node trie[max_nodes];
void insert( int root, long long num ) {
string digits = to_string(num);
digits = string(max_len - int(digits.size()), '0') + digits;
int cur = root;
for( int i = 0; i < max_len; i++ ) {
int j = digits[i] - '0';
if( trie[cur].nxt[j] == -1 ) {
assert(next_free + 1 < max_nodes);
trie[cur].nxt[j] = next_free++;
}
cur = trie[cur].nxt[j];
}
}
void init_trie( void ) {
for( int i = 0; i < max_nodes; i++ ) {
trie[i] = node();
}
next_free = 20;
}
long long query( int root, long long num ) {
long long ret = 0;
string digits = to_string(num);
digits = string(max_len - int(digits.size()), '0') + digits;
int cur = root;
for( int i = 0; i < max_len; i++ ) {
int d = digits[i] - '0';
int c = 9 - d;
for( int j = 0; j < 10; j++ ) {
if( trie[cur].nxt[c] != -1 ) {
break;
}
c = (c + 9) % 10;
}
ret = ret * 10 + (d + c) % 10;
cur = trie[cur].nxt[c];
}
return ret;
}
inline long long Xor( long long a, long long b ) {
long long ret = 0;
long long pw10 = 1;
for( int i = 1; i <= max_len; i++ ) {
ret += pw10 * ((a+b) % 10);
a /= 10;
b /= 10;
pw10 *= 10;
}
return ret;
}
int main( void ) {
int n, k;
scanf("%i %i", &n, &k);
assert(2 <= n && n <= 40);
assert(1 <= k && k <= n);
vector<long long> S[2];
S[0].resize(n/2);
for( int i = 0; i < n/2; i++ ) {
scanf("%lld", &S[0][i]);
}
S[1].resize(n-n/2);
for( int i = 0; i < n-n/2; i++ ) {
scanf("%lld", &S[1][i]);
}
bool empty[55];
fill(empty, empty+55, true);
init_trie();
int m = (int) S[1].size();
for( int mask = 0; mask < (1<<m); mask++ ) {
int sz = __builtin_popcount(mask);
if( sz > k ) continue;
long long cur = 0;
for( int j = 0; j < m; j++ ) {
if( mask & (1<<j) ) {
cur = Xor(cur, S[1][j]);
}
}
insert(sz, cur);
empty[sz] = false;
}
m = (int) S[0].size();
long long best = 0;
for( int mask = 0; mask < (1<<m); mask++ ) {
const int num_bits = 22;
int sz = __builtin_popcount(mask);
if( (sz > k) || empty[k-sz] ) continue;
long long cur = 0;
for( int j = 0; j < num_bits; j++ ) {
if( mask & (1<<j) ) {
cur = Xor(cur, S[0][j]);
}
}
best = max(best, query(k-sz, cur));
}
printf("%lldn", best);
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
int n, t;
int a[40];
int b[40][10];
int c[10];
vector<array<int, 10>> trie[21];
array<int, 10> zero;
void rec(int s, int e, int k)
{
if(s==e)
{
int cur=0;
for(int i=0; i<10; i++)
{
if(!trie[k][cur][c[i]])
{
trie[k][cur][c[i]]=trie[k].size();
trie[k].push_back(zero);
}
cur=trie[k][cur][c[i]];
}
}
else
{
rec(s+1, e, k);
for(int i=0; i<10; i++)
c[i]=(c[i]+b[s][i])%10;
rec(s+1, e, k+1);
for(int i=0; i<10; i++)
c[i]=(c[i]-b[s][i]+10)%10;
}
}
long long rec2(int s, int e, int k)
{
if(s==e)
{
k=t-k;
if(k<0 || k>20)
return 0;
long long ret=0;
int cur=0;
for(int i=0; i<10; i++)
{
int d=(10-c[i])%10;
ret*=10;
bool ok=false;
for(int j=9; j>=0; j--) if(trie[k][cur][(d+j)%10])
{
ret+=(d+j+c[i])%10;
cur=trie[k][cur][(d+j)%10];
ok=true;
break;
}
if(!ok)
return 0;
}
return ret;
}
else
{
long long ret=rec2(s+1, e, k);
for(int i=0; i<10; i++)
c[i]=(c[i]+b[s][i])%10;
ret=max(ret, rec2(s+1, e, k+1));
for(int i=0; i<10; i++)
c[i]=(c[i]-b[s][i]+10)%10;
return ret;
}
}
int main()
{
scanf("%d%d", &n, &t);
assert(1<=t && t<=n && n<=40);
for(int i=0; i<n; i++)
{
scanf("%d", a+i);
assert(0<=a[i] && a[i]<=1000000000);
for(int j=0; j<10; j++)
{
b[i][j]=a[i]%10;
a[i]/=10;
}
reverse(b[i], b[i]+10);
}
for(int i=0; i<21; i++)
trie[i].push_back(zero);
int m=n/2;
rec(0, m, 0);
printf("%lldn", rec2(m, n, 0));
return 0;
}