# HackerEarth Xoring in Base 10 problem solution

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("%lld\n", 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("%lld\n", rec2(m, n, 0));    return 0;}`