HackerRank Prime XOR problem solution

In this HackerRank Prime XOR problem solution Penny has an array of n integers, [a0,a1,…,an-1. She wants to find the number of unique multisets she can form using elements from the array such that the bitwise XOR of all the elements of the multiset is a prime number. Recall that a multiset is a set which can contain duplicate elements.

Given q queries where each query consists of an array of integers, can you help Penny find and print the number of valid multisets for each array? As these values can be quite large, modulo each answer by 10⁹ + 7 before printing it on a new line.

HackerRank Prime XOR problem solution in Python.

from collections import Counter
from math import sqrt
import re
import sys
import random
# Complete the primeXor function below.
def middle_out(counts):
    a = ((4096, 4351), (4352, 4500), (3584, 4095), (3500, 3583))
    b = ((256, 0), (512, 0), (512, 4096), (1024, 4096))
    divisor = 0
    count = [0]*4501
    for i,n in counts:
        count[i] = n

    sum = [[0]*8192 for _ in range(2)] 
    temp, update = 0, 1 
    sum[temp][0] = 1 
    divisor = 10**9 + 7
    for i,p in enumerate(a):
        for j,n in enumerate(count[p[0]:p[1]+1]):
            if n:
                temp2 = n//2 
                same = 1 + temp2
                change = (n+1)//2  
                o = b[i][1]
                for x in range(b[i][0]):  
                    y = x^(j+p[0])
                    sum[update][y] = (sum[temp][x]*change + sum[temp][y]*same)
                    sum[update][x] = (sum[temp][y]*change + sum[temp][x]*same)
                    
                    if o:
                        sum[update][y+o] = (sum[temp][x+o]*change + sum[temp][y+o]*same)
                        sum[update][x+o] = (sum[temp][y+o]*change + sum[temp][x+o]*same)
                        
                if sum[update][0] > 100000*divisor:  
                    for x in range(len(sum[update])):
                        sum[update][x] %= divisor
                temp, update = update, temp

    p = primes(8191)
    total = 0
    for prime in p:
        total += sum[temp][prime]
    return total % divisor

def primes(n):
    x = [True]*((n-1)//2)
    for i in range(int((sqrt(n)-3)//2)+1):
        if x[i]:
            x[2*i*i+6*i+3::2*i+3] = [False] * int((n-(2*i+3)**2)//(4*i+6)+1)
    return [2] + [2*i+3 for i,v in enumerate(x) if v]
q = int(input())
for _ in range(q):
    n = int(input())
    numbers = Counter(int(x) for x in input().split()).items()
    print(middle_out(numbers))

Prime XOR problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
    static final int N = 8192;
    static final int M = 1000000007;
    static HashSet<Integer> primes = new HashSet<Integer>();
    static long primeXor(int[] arr) {
        long[][] dp = new long[1001][N];
        int[] c = new int[1001];
        for (int i = 0; i < arr.length; i++)
            c[arr[i]-3500]++;
        
        dp[0][3500] = (c[0] + 1)/2;
        dp[0][0] = (c[0] + 2) / 2;
        for(int i = 1; i < 1001; i++) {
            for(int j = 0; j < N; j++) {
                dp[i][j] = (dp[i-1][j]*((c[i]+2)/2) + dp[i-1][j^(i+3500)]*((c[i]+1)/2)) % M;
            }
        }

        long ans = 0;
        for(int p : primes){
            ans = (ans + dp[1000][p]) % M;
        }
        return ans % M;
    }

    static void createPrimeSet() {
        boolean[] sieve = new boolean[N];
        for (int i = 2; i*i < N; i++) {
            if (sieve[i]) continue;
            for(int j = i+i; j < N; j+=i) {
                sieve[j] = true;
            }
        }
        for (int i = 2; i < N; i++) {
            if (sieve[i]) continue;
            primes.add(i);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        scanner.skip("(rn|[nru2028u2029u0085])?");

        createPrimeSet();
        for (int qItr = 0; qItr < q; qItr++) {
            int n = scanner.nextInt();
            scanner.skip("(rn|[nru2028u2029u0085])?");

            int[] a = new int[n];

            String[] aItems = scanner.nextLine().split(" ");
            scanner.skip("(rn|[nru2028u2029u0085])?");

            for (int i = 0; i < n; i++) {
                int aItem = Integer.parseInt(aItems[i]);
                a[i] = aItem;
            }

            long result = primeXor(a);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++.

#pragma comment(linker, ”/STACK:36777216“)
#include<bits/stdc++.h>

#define x first
#define y second
#define y0 hi1
#define y1 hi2
#define ll long long
#define mp make_pair
#define pb push_back
#define sqr(a) (a)*(a)
#define ld long double
#define all(a) (a).begin(), (a).end()

using namespace std;

const int inf = 2000000000;
const int md = 1e9 + 7;
const int N = 4501;

long long a[N], f1[2 * N], f2[2 * N];

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;

        memset(a, 0, sizeof(a));
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));

        for(int i = 0; i < n; i++){
            int x;
            cin >> x;
            a[x]++;
        }

        f1[0] = 1;
        for(int i = 3500; i <= 4500; i++){
            if(a[i]){
                for(int j = 0; j < 2 * N; j++){
                    if(f1[j]){
                        f2[j] = (f2[j] + f1[j] * (a[i] / 2 + 1)) % md;
                        f2[i^j] = (f2[i^j] + f1[j] * ((a[i] + 1) / 2)) % md;
                    }
                }
                for(int j = 0; j < 2 * N; j++){
                    swap(f1[j], f2[j]);
                    f2[j] = 0;
                }
            }
        }

        long long result = 0;
        for(int j = 2; j < 2 * N; j++){
            if(f1[j] == 0){
                continue;
            }
            int x = j;

            bool p = 1;
            for(int i = 2; i <= floor(sqrt(x)); i++){
                if(x % i == 0){
                    p = 0;
                    break;
                }
            }

            if(p){
                result = (result + f1[j]) % md;
            }
        }
        cout << result << "n";
    }
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
void gen_primes(int max,int*primes);
int a[1001],p[8192];
long long dp[1002][8192];

int main(){
  int q,n,x,i,j;
  long long ans;
  gen_primes(8191,p);
  scanf("%d",&q);
  while(q--){
    memset(a,0,sizeof(a));
    scanf("%d",&n);
    for(i=0;i<n;i++){
      scanf("%d",&x);
      a[x-3500]++;
    }
    for(i=0;i<8192;i++)
      dp[0][i]=0;
    dp[0][0]=1;
    for(i=0;i<1001;i++){
      for(j=0;j<8192;j++)
        dp[i+1][j]=dp[i][j];
      if(a[i])
        for(j=0;j<8192;j++){
          dp[i+1][j^(i+3500)]=(dp[i+1][j^(i+3500)]+dp[i][j]*((a[i]+1)/2))%MOD;
          dp[i+1][j]=(dp[i+1][j]+dp[i][j]*(a[i]/2))%MOD;
        }
    }
    for(i=ans=0;i<8192;i++)
      if(p[i])
        ans=(ans+dp[1001][i])%MOD;
    printf("%lldn",ans);
  }
  return 0;
}
void gen_primes(int max,int*primes){
  int i,j;
  for(i=0;i<=max;++i)
    primes[i]=1;
  primes[0]=primes[1]=0;
  for(i=2;i*i<=max;++i){
    if(!primes[i])
      continue;
    for(j=2;i*j<=max;++j)
      primes[i*j]=0;
  }
}