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.

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