HackerRank Prime Digit Sums Problem Solution Yashwant Parihar, June 23, 2023August 1, 2024 In this post, we will solve HackerRank Prime Digit Sums Problem Solution. Chloe is fascinated by prime numbers. She came across the number 283002 on a sign and, though the number is not prime, found some primes hiding in it by using the following rules: You must answer q queries, where each query consists of an integer, n. For each n, find and print the number of positive n-digit numbers, modulo 10 power 9 +7. that satisfy all three of Chloe’s rules (i.e., every three, four, and five consecutive digits sum to a prime).Input FormatThe first line contains an integer, q, denoting the number of queries.Each of the q subsequent lines contains an integer denoting the value of n for a query Sample Input 0 1 6 Sample Output 0 95 HackerRank Prime Digit Sums Problem Solution Prime Digit Sums C Solution #include <stdlib.h> #include <stdio.h> #include <math.h> #include <assert.h> typedef unsigned long long ull; typedef unsigned int ui; #define swap_(x, y) { ui *z = x; x = y; y = z; } #define ac 20 #define ec (18 * 18) #define mod 1000000007 #define brutec 13 ui brutes[] = {0,9,90,303,280,218,95,101,295,513,737,668,578}; // see haskell file ui as[ec * ac]; ui startv[] = {17,6,6,2,0,0,9,3,9,3,0,0,6,4,13,15,13,15}; ui endv[] = {5,11,11,26,20,20,7,7,7,5,24,24,5,5,2,2,2,1}; // 18x18 times 18x18 void multmm(ui *a, ui *b, ui *c) { for (int i = 0; i < 18; ++i) { for (int j = 0; j < 18; ++j) { ull x = 0; for (int k = 0; k < 18; ++k) { x += (ull)a[i * 18 + k] * (ull)b[k * 18 + j]; } c[i * 18 + j] = (ui)(x % mod); } } } // 18x18 times 18x1 void multmv(ui *a, ui *b, ui *c) { for (int i = 0; i < 18; ++i) { ull x = 0; for (int k = 0; k < 18; ++k) { x += (ull)a[i * 18 + k] * (ull)b[k]; } c[i] = (ui)(x % mod); } } // 1x18 times 18x1 ui inprod(ui *a, ui *b) { ull x = 0; for (int k = 0; k < 18; ++k) { x += (ull)a[k] * (ull)b[k]; } return (ui)(x % mod); } void copy(ui *a, ui *b, int n) { for (int i = 0; i < n; ++i) { a[i] = b[i]; } } void ini() { ui _a[] = {0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; ui _b[ec]; ui *a = _a, *b = _b; for (int i = 0; i < ac; ++i) { copy(&as[i * ec], a, ec); multmm(a, a, b); swap_(a, b); } } ui solve(int n) { if (n < brutec) { return brutes[n]; } n -= 12; ui _v[18], _u[18]; ui *v = _v, *u = _u; copy(v, startv, 18); ui *a = as; while (n) { if (n % 2) { multmv(a, v, u); swap_(v, u); } n /= 2; a += ec; } return inprod(v, endv); } int main() { ini(); int q; scanf("%d", &q); for (int i = 0; i < q; ++i) { int n; scanf("%d", &n); ui x = solve(n); printf("%u\n", x); } return 0; } Prime Digit Sums C++ Solution #ifdef NOT_DMOJ //secret header that provides answers to all questions #include"contest includes.h" #else //include everything header for GCC #include<bits/stdc++.h> #endif #pragma region template code using namespace std; template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using maxheap = priority_queue<T>; template<typename T> using dpair = pair<T, T>; typedef long long ll; typedef dpair<int> pii; typedef dpair<long long> pll; typedef dpair<float> pff; typedef dpair<double> pdd; template<class T1, class T2> istream& operator >> (istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second; } template<class T1, class T2> void operator+=(vector<T1> &v, const T2 &obj) { v.push_back(obj); } template<class T1> void operator+=(vector<T1> &v, const T1 &obj) { v.push_back(obj); } const int INF = 0x3f3f3f3f; const ll mod = 1e9+7; class range { public: range(int end) :_start(0), _end(end), _step(1) {} range(int start, int end) :_start(start), _end(end), _step(1) {} range(int start, int end, int step) :_start(start), _end(end), _step(step) {} class iterator { public: iterator(int v, int s) :val(v), step(s) {}; int operator*() const { return val; } int operator++() { return (val += step); } bool operator==(const range::iterator &iter) const { return val == iter.val && step == iter.step; } bool operator!=(const range::iterator &iter) const { return !(this->operator==(iter)); } private: int val; int step; }; range::iterator begin() { return{ _start, _step }; } range::iterator end() { return{ _end, _step }; } private: int _start, _end, _step; }; #pragma endregion const int MAXN = 4e5 + 2; bitset<MAXN> sieve; ll dp[2][MAXN]; bool valid(string str) { for (int a = 0; a + 3 <= str.size(); a++) { int sum = 0; for (int b = 0; b < 3; b++) { sum += str[a+b] - '0'; } if (sieve[sum]) { return false; } } for (int a = 0; a + 4 <= str.size(); a++) { int sum = 0; for (int b = 0; b < 4; b++) { sum += str[a+b] - '0'; } if (sieve[sum]) { return false; } } for (int a = 0; a + 5 <= str.size(); a++) { int sum = 0; for (int b = 0; b < 5; b++) { sum += str[a+b] - '0'; } if (sieve[sum]) { return false; } } return true; } int ans[MAXN]; vector<int> children[MAXN]; vector<int> valid_nums; int main() { #ifdef NOT_DMOJ freopen("text.txt", "r", stdin); #else cin.tie(0); cin.sync_with_stdio(0); #endif sieve[0] = true; sieve[1] = true; for (int a = 2; a < MAXN; a++) { if (!sieve[a]) { for (int b = 2 * a; b < MAXN; b += a) { sieve[b] = true; } } } for (int a = 1; a < 10000; a++) { string st = to_string(a); while (st.size() < 4) { st = '0' + st; } if (valid(st)) { valid_nums.push_back(a); for (int b = 0; b < 10; b++) { int val = a * 10 + b; string str = to_string(val); while (str.size() < 5) { str = '0' + str; } if (valid(str)) { children[a].push_back(val % 10000); //cout << a << " goes to " << val << "\n"; } } } } for (int i : valid_nums) { if (i >= 1000){ dp[0][i] = 1; } } int cur = 1; for (int a = 5; a < MAXN; a++, cur ^= 1) { ll tmp = 0; for (int i : valid_nums) { dp[cur][i] = 0; } for (int i : valid_nums) { for (int j : children[i]) { dp[cur][j] += dp[!cur][i]; dp[cur][j] %= mod; tmp += dp[!cur][i]; } } tmp %= mod; ans[a] = tmp; } /* int myans = 0; for (int a = 1000; a < 10000; a++) { if (valid(to_string(a))) { myans++; } } cout << "!" << myans << "!\n";*/ int Q; cin >> Q; while (Q--) { int x; cin >> x; if (x == 1) { cout << "9\n"; } else if (x == 2) { cout << "90\n"; } else if (x == 3) { cout << "303\n"; } else if (x == 4) { cout << "280\n"; } else { cout << ans[x] << "\n"; } } } Prime Digit Sums 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 'primeDigitSums' function below. * * The function is expected to return an INTEGER. * The function accepts INTEGER n as parameter. */ public static int[] res = doIt(); public static int primeDigitSums(int n) { return res[n]; } public static int[] doIt() { res =new int[400001]; long mod = 1000000007; long[][] ar = new long[2][]; ar[0]= new long[12] { 348, 260, 248, 134, 44, 464, 242, 80, 36, 300, 114, 92 }; ar[1] = new long[12]; res[1] = 9; res[2] = 90; res[3] = 303; res[4] = 280; res[5] = 218; res[6] = 95; res[7] = 101; res[8] = 295; res[9] = 513; res[10]= 737; res[11] = 668; res[12] = 578; res[13] = 1303; res[14] = 2449; res[15] = 3655; res[16] = 3965;res[17] = 3446;res[18] = 5778;res[19] = 11376; long x=1 ,y=0, mn; for (int i = 20; i < 400001; i++) { x ^= 1; y ^= 1; ar[y][0] = (ar[x][7] + ar[x][8] + ar[x][11]) % mod; ar[y][1] = ar[x][11]; ar[y][2] = (ar[x][9]+ar[x][6]) % mod; ar[y][3] = ar[x][9]; ar[y][4] = ar[x][10] ; ar[y][5] = ar[x][0]; ar[y][6] = ar[x][1]; ar[y][7] = ar[x][2]; ar[y][8] = ar[x][3]; ar[y][9] = ar[x][5]; ar[y][10] = ar[x][6]; ar[y][11] = (ar[x][7] *2) % mod; mn = (ar[y][0]+(ar[y][1]*4) % mod+(ar[y][2]*11) % mod+(ar[y][3]*9) % mod+(ar[y][4]*2) % mod+(ar[y][5]*2) % mod+(ar[y][6]*9) % mod+(ar[y][7]*4) % mod+ar[y][8]+(ar[y][9]*5) % mod+(ar[y][10]*8) % mod+ar[y][11]) % mod; res[i] = (int)mn; } return res; } } class Solution { public static void Main(string[] args) { TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true); int q = Convert.ToInt32(Console.ReadLine().Trim()); for (int qItr = 0; qItr < q; qItr++) { int n = Convert.ToInt32(Console.ReadLine().Trim()); int result = Result.primeDigitSums(n); textWriter.WriteLine(result); } textWriter.Flush(); textWriter.Close(); } } Prime Digit Sums Java Solution 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; } } } Prime Digit Sums JavaScript Solution 'use strict'; const fs = require('fs'); process.stdin.resume(); process.stdin.setEncoding('utf-8'); let inputString = ''; let currentLine = 0; process.stdin.on('data', inputStdin => { inputString += inputStdin; }); process.stdin.on('end', _ => { inputString = inputString.trim().split('\n').map(str => str.trim()); main(); }); function readLine() { return inputString[currentLine++]; } /* * Complete the primeDigitSums function below. */ const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] const modulo = Math.pow(10,9)+7 const results = [] const aValidFiver = { keys: [], follower: [], counter: [] } let validLength = 0 const testPrime = (test) => { return primes.includes(test.split('').reduce((sum, cur)=>sum+parseInt(cur), 0)) } const getResult3 = () => { let count = 0 for (let i=100;i<1000;i++) { const strNum = i.toString() if (testPrime(strNum)) { count++ } } return count } const getResult4 = () => { let count = 0 for (let i=1000;i<10000;i++) { const strNum = i.toString() if ( testPrime(strNum.substring(0, 3)) && testPrime(strNum.substring(1, 4)) && testPrime(strNum) ) { count++ } } return count } const buildValidFiver = () => { if (aValidFiver.keys.length === 0) { for (let i=200;i<100000;i++) { let test = i.toString().padStart(5,'0') if ( testPrime(test.substring(0, 3)) && testPrime(test.substring(1, 4)) && testPrime(test.substring(2, 5)) && testPrime(test.substring(0, 4)) && testPrime(test.substring(1, 5)) && testPrime(test) ) { aValidFiver.keys.push(test) aValidFiver.follower.push([]) aValidFiver.counter.push(test.startsWith('0') ? 0 : 1) } } for (let i = 0; i < aValidFiver.keys.length; i++) { const key = aValidFiver.keys[i] for (let j = 0; j < 10; j++){ const next = (key + j).substring(1) const indexNext = aValidFiver.keys.indexOf(next) if (indexNext >= 0) { aValidFiver.follower[i].push(indexNext) } } } } validLength = aValidFiver.keys.length } function primeDigitSums(n) { if (results.length === 0) { results.push(0) for (let i=1; i< 3; i++){ results.push(Math.pow(10,i)-Math.pow(10,i-1)) } results.push(getResult3()) results.push(getResult4()) buildValidFiver() results.push((aValidFiver.counter.reduce((counter, curr) => (counter+curr) % modulo, 0)) % modulo) } const startAddingResults = n >= results.length ? results.length : n + 1 for (let numDigits = startAddingResults; numDigits <= n; numDigits++) { aValidFiver.lastCounter = [].concat(aValidFiver.counter) aValidFiver.counter = new Array(validLength).fill(0) for (let index = 0; index < aValidFiver.counter.length; index++) { const curCount = aValidFiver.lastCounter[index] if (curCount) { for (let i = 0; i < aValidFiver.follower[index].length; i++) { const next = aValidFiver.follower[index][i] aValidFiver.counter[next] = aValidFiver.counter[next] + curCount % modulo } } } results.push((aValidFiver.counter.reduce((counter, curr) => (counter+curr) % modulo, 0)) % modulo) } return results[n] } function main() { const ws = fs.createWriteStream(process.env.OUTPUT_PATH); const q = parseInt(readLine(), 10); for (let qItr = 0; qItr < q; qItr++) { const n = parseInt(readLine(), 10); let result = primeDigitSums(n); ws.write(result + "\n"); } ws.end(); } Prime Digit Sums Python Solution mod = 10**9 + 7 A = [0,0,0,0,0,2,3,15,2,0] B = [0,0,0,0,0,4,9,13,17,2] results = [1,9,90,303,280,218,95,101,295] for _ in range(int(input())): n = int(input()) for i in range(len(A),n): A.append((2*(A[i-5] + B[i-5])) % mod) B.append((A[i-1] + A[i-5] + 2*B[i-5]) % mod) print(results[n] if n < 9 else (5*A[n-1] + 9*A[n-2] + 19*A[n-3] + 6*A[n-4] + 3*A[n-5] + 2*B[n-1] + 5*B[n-2] + 20*B[n-3] + 5*B[n-4] + 4*B[n-5]) % mod) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython