In this HackerRank Prime Digit Sums problem solution we have a query consists of an integer n and for each n find and print the number of positive n digits number modulo by 10 to power 9 plus 7. that satisfy all the three of Chloe’s rules means the every three four and five consecutive digits sum to a prime number.
Problem solution in Java.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
public class Solution {
static boolean[] P = new boolean[62];
static final long MOD = (long) Math.pow(10, 9) + 7l;
static Map<Integer, ThreeDigit> DIGITMAP = new HashMap<Integer, ThreeDigit>();
static Map<Long, Long> tab = new HashMap<Long, Long>();
static long[] depNUM = new long[400001];
static int NL = 400005;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
P[2] = true;
P[3] = true;
List<Integer> list = new ArrayList<Integer>();
list.add(2);
list.add(3);
for (int i = 5; i < 50; i += 6) {
int i1 = i;
int i2 = i + 2;
boolean bi1 = true;
boolean bi2 = true;
int se = (int) Math.sqrt(i2);
for (int p : list) {
if (i1 % p == 0)
bi1 = false;
if (i2 % p == 0)
bi2 = false;
if (p > se) {
break;
}
if (!bi1 && !bi2)
break;
}
if (bi1) {
P[i1] = true;
list.add(i1);
}
if (bi2) {
P[i2] = true;
list.add(i2);
}
}
for (int i = 2; i < 1000; i++) {
int temp = i / 100 + i / 10 % 10 + i % 10;
if (P[temp]) {
DIGITMAP.put(i, new ThreeDigit(i));
}
}
for (ThreeDigit td : DIGITMAP.values()) {
initDigit(td);
}
Map<Integer, Long> fourNums = new HashMap<Integer, Long>();
ThreeDigit[] tds = new ThreeDigit[1000];
int[] depSum = new int[NL + 1];
for (ThreeDigit td : DIGITMAP.values()) {
if (td.v > 100) {
fourNums.put(td.v, 1l);
depSum[3]++;
}
tds[td.v] = td;
}
depSum[1] = 9;
depSum[2] = 90;
for (int i = 4; i <= NL; i++) {
Map<Integer, Long> fourNums2 = new HashMap<Integer, Long>();
travel(fourNums, fourNums2, tds, depSum, i);
fourNums = fourNums2;
}
while (N-- > 0) {
System.out.println(depSum[sc.nextInt()]);
}
sc.close();
}
public static void travel(Map<Integer, Long> fourNums, Map<Integer, Long> fourNums2, ThreeDigit[] tds, int[] depSum,
int dep) {
for (Entry<Integer, Long> entry : fourNums.entrySet()) {
int fourNum = entry.getKey();
long num = entry.getValue();
int first = fourNum / 1000;
ThreeDigit td = tds[fourNum % 1000];
for (ThreeDigit ttd : td.set) {
if (P[first + td.threeSum + ttd.last]) {
depSum[dep] += num;
depSum[dep] %= MOD;
Long v = fourNums2.get(td.v * 10 + ttd.last);
if (v == null)
fourNums2.put(td.v * 10 + ttd.last, num);
else
fourNums2.put(td.v * 10 + ttd.last, (v + num) % MOD);
}
}
}
}
public static void initDigit(ThreeDigit td) {
for (int i = 0; i < 10; i++) {
if (P[td.threeSum + i] && P[td.twoSum + i]) {
ThreeDigit gettd = DIGITMAP.get(td.v % 100 * 10 + i);
if (!td.set.contains(gettd)) {
td.set.add(gettd);
}
}
}
}
public static class ThreeDigit {
private int v;
private int threeSum;
private int twoSum;
private int first;
private int last;
private Set<ThreeDigit> set = new HashSet<ThreeDigit>();
public void addNextDigit() {
}
public ThreeDigit(int v) {
this.v = v;
this.last = v % 10;
this.twoSum = this.last + v / 10 % 10;
this.threeSum = this.twoSum + v / 100;
this.first = this.v / 100;
}
public int hashCode() {
return this.v;
}
public boolean equals(Object o) {
ThreeDigit o1 = (ThreeDigit) o;
return this.v == o1.v;
}
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 415, Q = 4e5+5, MOD = 1e9+7;
bool prime[100];
int sum(int n){
if(n == 0)
return 0;
return sum(n/10)+n%10;
}
bool is_ok(int n){
return prime[sum(n)] && prime[sum(n/10)] && prime[sum(n%1000)];
}
bool conn(int a, int b){
return ((a%1000) == b/10 && prime[sum(a) + b%10]);
}
int table[Q];
bool vacuum(int x){
if(x < 100)
return true;
if(!prime[sum(x%1000)])
return false;
return true;
}
int solve(){
int n;
cin >> n;
return table[n];
}
vector<int> nodes;
vector<int> adj[N];
void prep(){
for(int n = 1; n <= 3; ++n){
int mx = 1;
for(int i = 0; i < n; ++i)
mx *= 10;
for(int i = mx/10; i < mx; ++i)
table[n] += vacuum(i);
}
vector<int> dp(N,0);
for(int i = 0; i < N; ++i)
if(nodes[i] >= 1000){
dp[i] = 1;
++table[4];
}
for(int i = 5; i < Q; ++i){
vector<int> nxt(N,0);
for(int j = 0; j < N; ++j)
for(int v : adj[j])
nxt[v] = (nxt[v]+dp[j])%MOD;
ll sum = 0;
for(int val : nxt)
sum += val;
table[i] = sum%MOD;
dp = nxt;
}
}
int main(){
fill(prime+2,prime+100,true);
for(int i = 2; i < 100; ++i)
if(prime[i])
for(int j = 2*i; j < 100; j += i)
prime[j] = false;
for(int i = 0; i < 10000; ++i)
if(is_ok(i))
nodes.push_back(i);
int ans = 0;
for(int i = 0; i < nodes.size(); ++i)
for(int j = 0; j < nodes.size(); ++j){
int a = nodes[i], b = nodes[j];
if(conn(a,b)){
adj[i].push_back(j);
// cout << i << ' ' << j << 'n';
}
}
prep();
int q;
cin >> q;
while(q--)
cout << solve() << 'n';
}
