HackerRank Lucky Numbers Problem Solution Yashwant Parihar, August 13, 2023August 1, 2024 In this post, we will solve HackerRank Lucky Numbers Problem Solution. A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between a and b inclusive, are lucky? For example, a = 20 and b = 25. Each number is tested below: digit digit squares value sum squares sum 20 2 4,0 4 21 3 4,1 5 22 4 4,4 8 23 5 4,9 13 24 6 4,16 20 25 7 4,25 29 We see that two numbers, 21, 23 and 25 are lucky. Note: These lucky numbers are not to be confused with Lucky Numbers Function Description Complete the luckyNumbers function in the editor below. It should return an integer that represents the number of lucky numbers in the given range. luckyNumbers has the following parameter(s): a: an integer, the lower range bound b: an integer, the higher range bound Input Format The first line contains the number of test cases T.Each of the next T lines contains two space-separated integers, a and b. Output Format Output T lines, one for each test case in the order given. Sample Input 2 1 20 120 130 Sample Output 4 1 Explanation For the first case, the lucky numbers are 11, 12, 14, and 16.For the second case, the only lucky number is 120. HackerRank Lucky Numbers Problem Solution Lucky Numbers C Solution #include "stdio.h" #define L 18 #define D 9 #define MAX1 (L*D) #define MAX2 (L*D*D) int prime[MAX2+1]; long long power[L+1], cnt[L+1][MAX1+1][MAX2+1]; void precompute() { int i, j, k, d; power[0] = 1; for( i = 1; i <= L; i++ ) power[i] = power[i-1] * ( D + 1 ); for( i = 2; i <= MAX2; i++ ) prime[i] = 1; for( i = 2; i <= MAX2; i++ ) if( prime[i] ) for( j = 2 * i; j <= MAX2; j += i ) prime[j] = 0; for( j = 0; j <= MAX1; j++ ) for( k = 0; k <= MAX2; k++ ) cnt[0][j][k] = prime[j] && prime[k]; for( i = 1; i <= L; i++ ) for( j = 0; j <= MAX1; j++ ) for( k = 0; k <= MAX2; k++ ) for( d = 0; d <= D; d++ ) if( j + d <= MAX1 && k + d * d <= MAX2 ) cnt[i][j][k] += cnt[i-1][j+d][k+d*d]; } long long ways_rec( long long n, int i, int s1, int s2 ) { if( i < 0 ) return 0; int d = n / power[i]; long long ans = ways_rec( n - d * power[i], i - 1, s1 + d, s2 + d * d ); while( --d >= 0 ) ans += cnt[i][s1+d][s2+d*d]; return ans; } long long ways( long long n ) { return ways_rec( n, L, 0, 0 ); } int main() { precompute(); long long a, b; int t; scanf( "%d", &t ); while(t--) { scanf( "%lld%lld", &a, &b ); printf( "%lld\n", ways( b + 1 ) - ways( a ) ); } } Lucky Numbers C++ Solution #include <bits/stdc++.h> using namespace std; typedef long long LL; const int max_num = 1458; const int max_sum = 162; const int max_length = 19; LL dp[max_length + 1][max_sum + 1][max_num + 1]; int digits[max_length + 1]; bool composite[max_num + 1]; int len; void get_primes(){ composite[0] = composite[1] = true; for(long long i = 2; i * i <= max_num; i++){ if(!composite[i]){ for(long long j = i * i; j <= max_num; j+= i){ composite[j] = true; } } } } LL rec(int pos, int s1, int s2, int chk) { if(pos == -1) return !composite[s1] && !composite[s2]; if(!chk && dp[pos][s1][s2] != -1) return dp[pos][s1][s2]; LL ans = 0; int end = chk ? digits[pos] : 9; for(int d = 0 ; d <= end; d++) { ans += rec(pos - 1 , s1 + d , s2 + d * d, chk && d == end); } if(!chk) dp[pos][s1][s2] = ans; return ans; } LL get_ans(LL num) { if(num == 0) return 0; len = 0; while(num){ digits[len++] = num % 10; num /= 10; } LL ans = rec(len - 1, 0, 0, 1); return ans; } int main() { ios::sync_with_stdio(false);cin.tie(0); int t; get_primes(); memset(dp,-1,sizeof(dp)); cin >> t; while(t--) { LL a, b; cin >> a >> b; cout << get_ans(b) - get_ans(a - 1) << endl; } return 0; } Lucky Numbers C Sharp Solution using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Lucky_Numbers_daa { class Program { static bool[] primes = new bool[2000]; static bool isprime(int n) { for (int i = 2; i * i <= n; i++) if ((n % i) == 0) return false; return true; } static long?[, ,] mem = new long?[200, 2000, 19]; static long dp(int sum, int sum_sq, int z) { if (mem[sum, sum_sq, z].HasValue) return mem[sum, sum_sq, z].Value; long count = 0; if (z == 0) count = (primes[sum] && primes[sum_sq]) ? 1 : 0; else for (int i = 0; i < 10; i++) count += dp(sum + i, sum_sq + i * i, z - 1); mem[sum, sum_sq, z] = count; return count; } static long LuckyUpto(long A) { long b = 0; long f = 1000000000000000000; int sum = 0; int sum_sq = 0; int z = 18; while (f > A) { f /= 10; z--; } long count = 0;// dp(0, 0, z); for (; z >= 0; z--) { for (int i = 0; i < 10; i++) { long max = b + f * (i + 1) - 1; if (A == max) { count += dp(sum + i, sum_sq + i * i, z); return count; } else if (A > max) { count += dp(sum + i, sum_sq + i * i, z); } else { sum += i; sum_sq += i * i; b += i * f; f /= 10; break; } } } return count; } static void Main(string[] args) { for (int i = 2; i < primes.Length; i++) primes[i] = isprime(i); int T = int.Parse(Console.ReadLine()); for (int i = 0; i < T; i++) { string[] line = Console.ReadLine().Split(); long A = long.Parse(line[0]); long B = long.Parse(line[1]); if (A == 1000000000000000000) A--; if (B == 1000000000000000000) B--; Console.WriteLine(LuckyUpto(B) - LuckyUpto(A - 1)); } } } } Lucky Numbers Java Solution import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { /* * Complete the luckyNumbers function below. */ static long luckyNumbers(long a, long b) { return Method1.luckyNumbers(a, b); } static class Method1 { static final int max_bit = 19; static final int max_digit_sum = 9 * 18 + 1; static final int max_squre_digit_sum = 9 * 9 * 18 + 1; static long[][][] sum = new long[max_bit][max_digit_sum][max_squre_digit_sum]; static long[][][] left_sum = new long[max_bit][max_digit_sum][max_squre_digit_sum]; static boolean[] is_prime = new boolean[max_squre_digit_sum]; static long[] bit_sum = new long[max_bit]; static int tot = 231, max1, max2; static int[] prime = new int[tot]; static { Arrays.fill(is_prime, true); int ct = 0; is_prime[0] = is_prime[1] = false; for (int i = 2; i < max_squre_digit_sum; i++) if (is_prime[i]) { for (int j = i + i; j < max_squre_digit_sum; j += i) is_prime[j] = false; prime[ct++] = i; if (i < max_digit_sum) max1 = Math.max(max1, i); max2 = Math.max(max2, i); } sum[0][0][0] = 1; for (int i = 0; prime[i] <= max1; i++) for (int j = 0; j < tot && prime[j] <= max2; j++) { left_sum[0][prime[i]][prime[j]] += 1; } for (int i = 0; i < max_bit - 1; i++) { for (int next = 0; next < 10; next++) { for (int j = 0; j + next < max_digit_sum; j++) for (int k = 0; k + next * next < max_squre_digit_sum; k++) { sum[i + 1][j + next][k + next * next] += sum[i][j][k]; if (next > 0 && is_prime[j + next] && is_prime[k + next * next]) bit_sum[i + 1] += sum[i][j][k]; } for (int j = next; j < max_digit_sum; j++) for (int k = next * next; k < max_squre_digit_sum; k++) { left_sum[i + 1][j - next][k - next * next] += left_sum[i][j][k]; } } } } static long luckyNumbers(long a, long b) { return go(b) - go(a - 1); } static long go(long N) { if (N == 0) return 0; long ret = 0; boolean first = true; int pre_digit_sum = 0, pre_sdigit_sum = 0; for (int i = 19; i > 0; i--) { int bit = get_bit(N, i - 1); int least; if (bit != 0 && first) { least = 1; first = false; for (int j = 1; j < i; j++) ret += bit_sum[j]; } else { least = 0; } for (int nbit = least; nbit < bit; nbit++) { int digit_sum = pre_digit_sum + nbit; int sdigit_sum = pre_sdigit_sum + nbit * nbit; ret += left_sum[i - 1][digit_sum][sdigit_sum]; } pre_digit_sum += bit; pre_sdigit_sum += bit * bit; } if (is_prime[pre_digit_sum] && is_prime[pre_sdigit_sum]) ret += 1; return ret; } static int get_bit(long n, int m) { for (int i = 0; i < m; i++) n /= 10; return (int) (n % 10); } } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int t = Integer.parseInt(scanner.nextLine().trim()); for (int tItr = 0; tItr < t; tItr++) { String[] ab = scanner.nextLine().split(" "); long a = Long.parseLong(ab[0].trim()); long b = Long.parseLong(ab[1].trim()); long result = luckyNumbers(a, b); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); } bufferedWriter.close(); } } Lucky Numbers Python Solution def lucky(N): p = [int(x) for x in str(N)] numDigits = len(p) total = 0 curSum = 0 curSumSq = 0 while len(p): for a in range(p[0]): total += resolve(numDigits - 1, curSum + a, curSumSq + a**2) numDigits -= 1 curSum += p[0] curSumSq += p[0]**2 p.pop(0) return total def resolve(n, s, sq): if (n,s,sq) in memo: return memo[(n,s,sq)] if n == 0: if s in primes and sq in primes: memo[(n,s,sq)] = 1 return 1 memo[(n,s,sq)] = 0 return 0 c = 0 for b in range(10): c += resolve(n-1, s + b, sq + b**2) memo[(n,s,sq)] = c return c memo = {} primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999]) for test in range(int(input())): [A,B] = [int(x) for x in input().split(' ')] print(lucky(B+1)-lucky(A)) c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython