Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Xoring in Base 10 problem solution

YASH PAL, 31 July 2024
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

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;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes