In this HackerRank Prime XOR problem solution we have 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 to power 9 plus 7 before printing it on a new line.
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))
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("(\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();
}
}
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("%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;
}
}
0 Comments