Table of Contents
Lucky Numbers – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include<iostream>
#include<set>
#include<map>
#include<string>
#include<stdio.h>
#include<sstream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<string.h>
using namespace std ;
#define MAXN 2000
#define INF (int)1e9
bool sieve[MAXN] ;
void generate()
{
for(int tt = 0;tt < 10;tt++)
{
char in[] = "in .txt" ;
in[2] = tt + '0' ;
FILE * fout = fopen(in,"w") ;
int n,p,runs ;
runs = 10000 ;
fprintf(fout,"%d\n",runs) ;
for(int i = 0;i < runs;i++)
{
int L = 1000000000 ;
long long a = 1LL * (rand() % L) * (rand() % L) + 1 ;
long long b = 1LL * (rand() % L) * (rand() % L) + 1 ;
if(rand() % 10 == 0) a = rand() % L + 1 ;
if(a > b) swap(a,b) ;
fprintf(fout,"%lld %lld\n",a,b) ;
}
}
}
int brute(int a,int b)
{
int ret = 0 ;
for(int i = a;i <= b;i++)
{
int sum1 = 0,sum2 = 0 ;
for(int temp = i;temp > 0;temp /= 10) { sum1 += temp % 10 ; sum2 += (temp % 10) * (temp % 10) ; }
if(sieve[sum1] && sieve[sum2]) ret++ ;
}
return ret ;
}
int d,D[20] ;
long long memo[20][200][2000] ;
long long solve(int k,int st,int sum1,int sum2)
{
if(k == -1) return sieve[sum1] && sieve[sum2] ? 1 : 0 ;
if(st == 0 && memo[k][sum1][sum2] != -1) return memo[k][sum1][sum2] ;
long long ret = 0 ;
for(int i = 0;i < 10;i++) if(!st || i <= D[k])
{
ret += solve(k - 1,st && i == D[k] ? 1 : 0,sum1 + i,sum2 + i * i) ;
}
if(st == 0) memo[k][sum1][sum2] = ret ;
return ret ;
}
long long solve(long long n)
{
d = 0 ;
while(n > 0)
{
D[d++] = n % 10 ;
n /= 10 ;
}
long long ret = 0 ;
for(int i = d - 1;i >= 0;i--)
for(int j = 1;j < 10;j++)
if(i < d - 1 || j <= D[i])
ret += solve(i - 1,i == d - 1 && j == D[i],j,j * j) ;
return ret ;
}
int main()
{
for(int i = 2;i < MAXN;i++) sieve[i] = true ;
for(int i = 2;i < MAXN;i++)
for(int j = i + i;j < MAXN;j += i)
sieve[j] = false ;
memset(memo,255,sizeof memo) ;
// generate() ; return 0 ;
int runs ;
cin >> runs ;
while(runs--)
{
long long a,b ;
cin >> a >> b ;
if(a < 1 || a > b || b > 1000000000000000000LL) { cout << "bad input\n" ; return 1 ; }
long long ret = solve(b) ;
if(a > 1) ret -= solve(a - 1) ;
cout << ret << endl ;
// cout << brute(a,b) << endl ;
}
return 0 ;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;
public class Solution implements Runnable {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
static int MAX_LEN = 18;
static int MAX_SUM_SQ = MAX_LEN * 9 * 9 + 1;
static boolean[] IS_PRIME;
static int PRIME_COUNT;
static int[] PRIMES;
static long[][][][] D_COUNT, D_CACHE;
static int[][][] DC_MIN, DC_MAX;
static int[] FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM;
static int[][] P1_HI, P2_HI;
static long timePrecalc;
static {
long timeStart = System.currentTimeMillis();
IS_PRIME = new boolean[MAX_SUM_SQ];
Arrays.fill(IS_PRIME, true);
IS_PRIME[0] = false;
IS_PRIME[1] = false;
PRIME_COUNT = 0;
for (int i = 2; i < MAX_SUM_SQ; i++)
if (IS_PRIME[i]) {
PRIME_COUNT++;
for (int j = i + i; j < MAX_SUM_SQ; j += i) {
IS_PRIME[j] = false;
}
}
PRIMES = new int[PRIME_COUNT];
for (int i = 2, idx = 0; i < MAX_SUM_SQ; i++)
if (IS_PRIME[i]) {
PRIMES[idx++] = i;
}
// save memory by smart allocation
D_COUNT = new long[10][MAX_LEN + 1][][];
for (int digitHigh = 0; digitHigh <= 9; digitHigh++) {
long[][][] d = D_COUNT[digitHigh];
for (int i = 0; i <= MAX_LEN; i++) {
d[i] = new long[i * 9 + 1][i * 9 * 9 + 1];
}
// run dp
d[0][0][0] = 1;
for (int i = 0; i < MAX_LEN; i++)
for (int sum = 0; sum < d[i].length; sum++)
for (int sumSq = 0; sumSq < d[i][sum].length; sumSq++)
if (d[i][sum][sumSq] > 0) {
int hi = (i == 0) ? digitHigh : 9;
for (int k = 0; k <= hi; k++) {
d[i + 1][sum + k][sumSq + k * k] += d[i][sum][sumSq];
}
}
}
// save memory by smart allocation
D_CACHE = new long[10][MAX_LEN + 1][][];
for (int digitHigh = 0; digitHigh <= 9; digitHigh++) {
long[][][] d = D_CACHE[digitHigh];
for (int i = 0; i <= MAX_LEN; i++) {
d[i] = new long[(MAX_LEN - i) * 9 + 1][(MAX_LEN - i) * 9 * 9 + 1];
}
}
for (long[][][] v1 : D_CACHE)
for (long[][] v2 : v1)
for (long[] v3 : v2) {
Arrays.fill(v3, -1);
}
FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM = new int[MAX_SUM_SQ];
P1_HI = new int[MAX_SUM_SQ][MAX_LEN + 1];
P2_HI = new int[MAX_SUM_SQ][MAX_LEN + 1];
for (int i = 0; i < MAX_SUM_SQ; i++) {
// first prime >= i
FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[i] = -1;
for (int j = 0; j < PRIME_COUNT; j++)
if (PRIMES[j] >= i) {
FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[i] = j;
break;
}
Arrays.fill(P1_HI[i], -1);
for (int len = 0; len <= MAX_LEN; len++) {
int dLen = D_COUNT[0][len].length;
for (int j = 0; j < PRIME_COUNT; j++)
if (PRIMES[j] - i < dLen) {
P1_HI[i][len] = j;
}
}
Arrays.fill(P2_HI[i], -1);
for (int len = 0; len <= MAX_LEN; len++) {
int dLen = D_COUNT[0][len][0].length;
for (int j = 0; j < PRIME_COUNT; j++)
if (PRIMES[j] - i < dLen) {
P2_HI[i][len] = j;
}
}
}
DC_MIN = new int[10][MAX_LEN + 1][];
DC_MAX = new int[10][MAX_LEN + 1][];
for (int digitHigh = 0; digitHigh <= 9; digitHigh++)
for (int i = 0; i <= MAX_LEN; i++) {
int p1Len = D_COUNT[digitHigh][i].length;
DC_MIN[digitHigh][i] = new int[p1Len];
DC_MAX[digitHigh][i] = new int[p1Len];
for (int p1 = 0; p1 < p1Len; p1++) {
int lo = Integer.MAX_VALUE;
int hi = Integer.MIN_VALUE;
int p2Len = D_COUNT[digitHigh][i][p1].length;
for (int p2 = 0; p2 < p2Len; p2++)
if (D_COUNT[digitHigh][i][p1][p2] > 0) {
lo = Math.min(lo, p2);
hi = Math.max(hi, p2);
}
DC_MIN[digitHigh][i][p1] = lo;
DC_MAX[digitHigh][i][p1] = hi;
}
}
for (int p1 = 0; p1 < MAX_SUM_SQ; p1++)
for (int p2 = 0; p2 < MAX_SUM_SQ; p2++)
timePrecalc = System.currentTimeMillis() - timeStart;
}
private void solve() throws IOException {
// stress();
// timing();
int tc = nextInt();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
long a = nextLong();
long b = nextLong();
out.println(solveFast(a, b));
}
}
private void stress() {
int maxN = 1000;
for (int a = 1; a <= maxN; a++) {
System.out.println("Stress (A): " + a);
for (int b = a; b <= maxN; b++) {
long ans1 = solveFast(a, b);
long ans2 = solveNaive(a, b);
if (ans1 != ans2) {
throw new IllegalStateException(a + " - " + b + ": " + ans1 + " vs. " + ans2);
}
}
}
Random r = new Random(123456789L);
int maxTc = 400;
long lo = 0;
long hi = 1000000000000000000L;
for (int tc = 0; tc < maxTc; tc++) {
System.out.println("Stress (B): " + tc);
long a = r.nextLong();
a %= hi;
if (a < 0) {
a += hi;
}
if (a < lo || a > hi) {
throw new IllegalStateException();
}
int len = r.nextInt(1000000);
long b = Math.min(a + len, hi);
long ans1 = solveFast(a, b);
long ans2 = solveNaive(a, b);
if (ans1 != ans2) {
throw new IllegalStateException(a + " - " + b + ": " + ans1 + " vs. " + ans2);
}
}
System.err.println("Stress test passed");
}
private void timing() {
int tc = 10000;
Random r = new Random();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
long a = randomLong(r);
long b = randomLong(r);
if (a > b) {
long t = a; a = b; b = t;
}
solveFast(a, b);
}
System.err.println("Timing test finished");
}
private long randomLong(Random r) {
long a = 0;
int len = 18 + r.nextInt(1);
for (int i = 0; i < len; i++) {
int digit = r.nextInt(10);
while (i == 0 && digit == 0) {
digit = r.nextInt(10);
}
a *= 10;
a += digit;
}
if (a < 0 || a > 1000000000000000000L) {
throw new IllegalStateException();
}
return a;
}
// [lo, hi] [0, 9] ... [0, 9] - has length 'len' digits
private long solveFast(int firstDigitHi, int len, int sumInit, int sumSqInit) {
if (firstDigitHi < 0) {
return 0;
}
if (len == 19) {
// the only way to get here is 10^18
// returning pre-calculated value to save some memory on the D_COUNT array
return 65931412787268351L;
}
if (D_CACHE[firstDigitHi][len][sumInit][sumSqInit] != -1) {
return D_CACHE[firstDigitHi][len][sumInit][sumSqInit];
}
/*
long[][] d = D_COUNT[firstDigitHi][len];
long result = 0;
for (int sum = 0; sum < d.length; sum++)
if (IS_PRIME[sum + sumInit])
for (int sumSq = 0; sumSq < d[sum].length; sumSq++)
if (IS_PRIME[sumSq + sumSqInit]) {
result += d[sum][sumSq];
}
*/
/*
long[][] d = D_COUNT[firstDigitHi][len];
long result = 0;
int p1Lo = FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[sumInit];
int p1Hi = P1_HI[sumInit][len];
int p2Lo = FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[sumSqInit];
int p2Hi = P2_HI[sumSqInit][len];
for (int p1Idx = p1Lo; p1Idx <= p1Hi; p1Idx++) {
int p1 = PRIMES[p1Idx] - sumInit;
for (int p2Idx = p2Lo; p2Idx <= p2Hi; p2Idx++) {
int p2 = PRIMES[p2Idx] - sumSqInit;
result += d[p1][p2];
}
}
*/
long[][] d = D_COUNT[firstDigitHi][len];
long result = 0;
int p1Lo = FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[sumInit];
int p1Hi = P1_HI[sumInit][len];
for (int p1Idx = p1Lo; p1Idx <= p1Hi; p1Idx++) {
int p1 = PRIMES[p1Idx] - sumInit;
int lo = DC_MIN[firstDigitHi][len][p1];
int hi = DC_MAX[firstDigitHi][len][p1];
if (lo > hi) {
continue;
}
int p2Idx = FIRST_PRIME_IDX_GREATER_OR_EQ_THAN_SUM[lo + sumSqInit];
while (p2Idx < PRIME_COUNT) {
int p2 = PRIMES[p2Idx] - sumSqInit;
if (p2 > hi) {
break;
}
result += d[p1][p2];
p2Idx++;
}
/*
for (int p2 = lo; p2 <= hi; p2++)
if (IS_PRIME[p2 + sumSqInit]) {
result += d[p1][p2];
}
*/
}
D_CACHE[firstDigitHi][len][sumInit][sumSqInit] = result;
return result;
}
// [0, a]
private long solveFast(long a) {
if (a < 1) {
return 0;
}
long total = 0;
// count the right boundary first, and then solve [0, a-1]
if (isLucky(a)) {
total++;
}
int len = Long.toString(a).length();
int[] d = new int[len];
for (int i = len - 1; i >= 0; i--) {
d[i] = (int) (a % 10);
a /= 10;
}
// 100
// [000 - 099], prefixLen = 0, firstDigit = 0..0
// [100 - ], prefixLen = 1, firstDigit = 0..-1
// [100 - ], prefixLen = 2, firstDigit = 0..-1
// [100]
// 2514
// [0000 - 1999], prefixLen = 0, firstDigit = 0..1
// [2000 - 2499], prefixLen = 1, firstDigitHi = 0..4
// [2500 - 2509], prefixLen = 2, firstDigitHi = 0..0
// [2510 - 2513], prefixLen = 3, firstDigitHi = 0..3
// [2514]
int sum = 0;
int sumSq = 0;
for (int prefixLen = 0; prefixLen < len; prefixLen++) {
total += solveFast(d[prefixLen] - 1, len - prefixLen, sum, sumSq);
sum += d[prefixLen];
sumSq += d[prefixLen] * d[prefixLen];
}
return total;
}
// [a, b]
private long solveFast(long a, long b) {
return solveFast(b) - solveFast(a - 1);
}
private long solveNaive(long a, long b) {
long res = 0;
for (long k = a; k <= b; k++)
if (isLucky(k)) {
res++;
}
return res;
}
private boolean isLucky(long k) {
int sum = 0;
int sumSq = 0;
while (k > 0) {
int d = (int) (k % 10);
sum += d;
sumSq += d * d;
k /= 10;
}
return IS_PRIME[sum] && IS_PRIME[sumSq];
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new FileWriter(FILE_OUT));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timePrecalc + timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def is_prime(x):
if x in (0, 1):
return False
i = 2
while i*i <= x:
if x % i == 0:
return False
i += 1
return True
prime = map(is_prime, xrange(0,2000))
cache = {}
digits = range(0, 10)
def rec_scan(key):
(x, a, b) = key
if x == 1:
count = 0
for d in digits:
if prime[a + d] and prime[b + d*d]:
count += 1
else:
count = 0
for d in digits:
subkey = (x - 1, a + d, b + d*d)
if subkey in cache:
count += cache[subkey]
else:
count += rec_scan(subkey)
cache[key] = count
return count
def full_scan(x, a, b):
key = (x, a, b)
if key in cache:
return cache[key]
return rec_scan(key)
def partial_scan(x, q):
m = q % 10
q /= 10
a = 0
b = 0
while q > 0:
t = q % 10
a += t
b += t*t
q /= 10
if x == 1:
count = 0
for d in xrange(0, m):
if prime[a + d] and prime[b + d*d]:
count += 1
else:
count = 0
for d in xrange(0, m):
count += full_scan(x - 1, a + d, b + d*d)
return count
top_cache = {}
def solve(x):
key = x
if key in top_cache:
return top_cache[key]
x += 1
if x in top_cache:
return top_cache[x]
level = 1
result = 0
while x > 0:
result += partial_scan(level, x)
level += 1
x /= 10
top_cache[key] = result
return result
def calculate(low, high):
return solve(high) - solve(low - 1)
count = int(raw_input())
while count > 0:
count -= 1
(low, high) = [ int(i) for i in raw_input().split(' ') if i != '' ]
print calculate(low, high)
C rep HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1460];
unsigned long long dyn_table[20][164][1460];
//changed here.......1
unsigned long long ans[19][10][164][1460]; //about 45 MB
int start[19][163];
int end[19][163];
//upto here.........1
void gen_primes() {
for (int i = 0; i <= MAX_SQUARE_SUM; ++i) {
primes[i] = 1;
}
primes[0] = primes[1] = 0;
for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) {
if (!primes[i]) {
continue;
}
for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) {
primes[i*j] = 0;
}
}
}
void gen_table() {
for (int i = 0; i <= MAX_LENGTH; ++i) {
for (int j = 0; j <= MAX_SUM; ++j) {
for (int k = 0; k <= MAX_SQUARE_SUM; ++k) {
dyn_table[i][j][k] = 0;
}
}
}
dyn_table[0][0][0] = 1;
for (int i = 0; i < MAX_LENGTH; ++i) {
for (int j = 0; j <= 9 * i; ++j) {
for (int k = 0; k <= 9 * 9 * i; ++k) {
for (int l = 0; l < 10; ++l) {
dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k];
}
}
}
}
}
unsigned long long count_lucky (unsigned long long maxp) {
unsigned long long result = 0;
int len = 0;
int split_max[MAX_LENGTH];
while (maxp) {
split_max[len] = maxp % 10;
maxp /= 10;
++len;
}
int sum = 0;
int sq_sum = 0;
unsigned long long step_result;
unsigned long long step_;
for (int i = len-1; i >= 0; --i) {
step_result = 0;
int x1 = 9*i;
for (int l = 0; l < split_max[i]; ++l) {
//changed here........2
step_ = 0;
if(ans[i][l][sum][sq_sum]!=0)
{
step_result +=ans[i][l][sum][sq_sum];
continue;
}
int y = l + sum;
int x = l*l + sq_sum;
for (int j = 0; j <= x1; ++j) {
if(primes[j + y])
for (int k=start[i][j]; k<=end[i][j]; ++k) {
if (primes[k + x]) {
step_result += dyn_table[i][j][k];
step_+=dyn_table[i][j][k];
}
}
}
ans[i][l][sum][sq_sum] = step_;
//upto here...............2
}
result += step_result;
sum += split_max[i];
sq_sum += split_max[i] * split_max[i];
}
if (primes[sum] && primes[sq_sum]) {
++result;
}
return result;
}
int main(int argc, char** argv) {
gen_primes();
gen_table();
//changed here..........3
for(int i=0;i<=18;i++)
for(int j=0;j<=163;j++)
{
for(int k=0;k<=1458;k++)
if(dyn_table[i][j][k]!=0ll)
{
start[i][j] = k;
break;
}
for(int k=1460;k>=0;k--)
if(dyn_table[i][j][k]!=0ll)
{
end[i][j]=k;
break;
}
}
//upto here..........3
int cases = 0;
scanf("%d",&cases);
for (int i = 0; i < cases; ++i) {
unsigned long long a, b;
scanf("%lld %lld", &a, &b);
//changed here......4
if(b == 1000000000000000000ll)
b--;
//upto here.........4
printf("%lld\n", count_lucky(b) - count_lucky(a-1));
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
