HackerRank Prime Digit Sums problem solution

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';
}