HackerRank Prime XOR Problem Solution

In this post, we will solve HackerRank Prime XOR Problem Solution.

Penny has an array of n integers, [ao, 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 a 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 109 + 7 before printing it on a new line.
Input Format
The first line contains a single integer, q, denoting the number of queries. The 2. q subsequent lines describe each query in the following format:

The first line contains a single integer, n, denoting the number of integers in the array.
The second line contains n space-separated integers describing the respective values of
a0, a1, an-1.

Output Format

On a new line for each query, print a single integer denoting the number of unique multisets Penny can construct using numbers from the array such that the bitwise XOR of all the multiset’s elements is prime. As this value is quite large, your answer must be modulo 10 power 9 + 7.

Sample Input

1   
3   
3511 3671 4153

Sample Output

Table of Contents

Prime XOR C Solution

#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("%lld\n",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;
  }
}

Prime XOR C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int mod = 1000000007;
bool sieve[9000];
int cnt[4505], q, n, arr[100005];
int memo[1005][9000];
int dp(int pos, int val) {
    if (pos ==  1001) return sieve[val];
    int &ret = memo[pos][val];
    if (ret != -1) return ret;
    ret = 0;
    long long numeven = cnt[pos+3500] / 2;
    long long numodd = cnt[pos+3500] - numeven;
    if (numodd > 0) {
        ret += ((numodd * dp(pos + 1, val ^ (pos + 3500))) % mod);
        ret %= mod;
    }
    if (numeven > 0) {
        ret += ((numeven * dp(pos + 1, val)) % mod);
        ret %= mod;
    }
    
    ret += dp(pos + 1, val);
    ret %= mod;
    return ret;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    memset(sieve, true, sizeof(sieve));
    sieve[0] = sieve[1] = false;
    for (int i = 2; i < 9000; i++) {
        if (sieve[i]) {
            for (int j = i + i; j < 9000; j += i)
                sieve[j] = false;
        }
    }
    cin>>q;
    for (int i = 1; i <= q; i++) {
        memset(memo,-1,sizeof(memo));
        memset(cnt,0,sizeof(cnt));
        cin>>n;
        for (int j = 1; j <= n; j++) {
            cin >> arr[i];
            ++cnt[arr[i]];
        }
        printf("%d\n",dp(0,0));
    }
    return 0;
}

Prime XOR C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'primeXor' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY a as parameter.
     */
    private static int N = 8192;
        private static int M = 1000000007;
        
    
    public static long primeXor(List<int> a,  HashSet<int> primes)
        {
            
            
            long[,] dp = new long[2,N];
            int[] c = new int[1001];
            for (int i = 0; i < a.Count; i++)
                c[a[i] - 3500]++;
            int f = 1;
            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[f,j] = (dp[f ^1, j] * ((c[i] + 2) / 2) + dp[f ^ 1, j ^ (i + 3500)] * ((c[i] + 1) / 2)) % M;
                }
                f = f ^ 1;
            }
            
            long ans = 0;
            foreach (var p in primes)
            {
                ans = (ans + dp[f,p]) % M;
               
            }
            
            return ans % M;
        }
    
}

class Solution
{
     private static HashSet<int> primes = new HashSet<int>();
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
        
        createPrimeSet();
        int q = Convert.ToInt32(Console.ReadLine().Trim());

        for (int qItr = 0; qItr < q; qItr++)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());

            List<int> a = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(aTemp => Convert.ToInt32(aTemp)).ToList();

            long result = Result.primeXor(a, primes);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
    private static void createPrimeSet()
        {
            bool[] sieve = new bool[8192];
            for (int i = 2; i * i < 8192; i++)
            {
                if (sieve[i]) continue;
                for (int j = i + i; j < 8192; j += i)
                {
                    sieve[j] = true;
                }
            }
            for (int i = 2; i < 8192; i++)
            {
                if (sieve[i]) continue;
                primes.Add(i);
            }
        }

    
}

Prime XOR Java Solution

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("(\r\n|[\n\r\u2028\u2029\u0085])?");

        createPrimeSet();
        for (int qItr = 0; qItr < q; qItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] a = new int[n];

            String[] aItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            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();
    }
}

Prime XOR JavaScript Solution

'use strict';

const LIMIT = (2 ** 13) + 1;
const MOD = (10 ** 9) + 7;
const LOWER_BOUND = 3500;
const UPPER_BOUND = 4500;
const RANGE_SIZE = (UPPER_BOUND - LOWER_BOUND) + 1;

function debug(message) {
  console.log("DEBUG: " + message);
}
const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) { inputString += inputStdin; });

process.stdin.on('end', function() { inputString = inputString.split('\n'); main(); });

function readLine() { return inputString[currentLine++]; }

function calcPrimes() {
  const primes = Array(LIMIT).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i < LIMIT; i++) {
    for (let j = i*2; j < LIMIT; j += i) {
      primes[j] = false;
    }
  }
  return primes;
}

function calcHistorgram(xs) {
  const histogram = Array(RANGE_SIZE).fill(0);
  for (let i = 0; i < xs.length; i++) {
    let adjustedKey = xs[i] - LOWER_BOUND;
    histogram[adjustedKey] += 1;
  }
  return histogram;
}

function calcSum(counts) {
  const primes = calcPrimes();
  let sum = 0;
  for (let i = 0; i < LIMIT; i++) {
    if (primes[i]) {
      sum = (sum + counts[i]) % MOD;
    }
  }
  return sum;
}

function computeCounts(histogram) {
  let dp = Array(LIMIT).fill(0);
  dp[0] = 1;
  for (let i = 0; i < histogram.length; i++) {
    const cnt = histogram[i];
    if (cnt == 0) { continue; }
    const originalValue = i + LOWER_BOUND; 
    const evens = Math.floor(cnt / 2);
    const odds = Math.floor((1 + cnt) / 2);
    const temp = dp.slice();
    for (let j = 0; j < LIMIT; j++) {
      if (dp[j] == 0) { continue; }
      const xor = originalValue ^ j;
      temp[j] += (dp[j] * evens) % MOD
      temp[xor] += (dp[j] * odds) % MOD
    }
    dp = temp;
  }
  return dp;
}

function solve(xs) {
  const histogram = calcHistorgram(xs);
  const counts = computeCounts(histogram);
  const sum = calcSum(counts); 
  return sum;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
    const t = parseInt(readLine(), 10);
    for (let i = 0; i < t; i++) {
      const n = parseInt(readLine(), 10);
      const xs = readLine().split(" ").map(x => parseInt(x, 10));
      const answer = solve(xs);
      ws.write(answer + '\n');
    }
    ws.end();
}

Prime XOR Python Solution

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))