# HackerEarth- Spini Java Hiring Challenge

Hiring Challenge Problem. Any ideas for the solution.

P.S.–>> The “later later later” one Post is this.

1 Like

Still 2 hours are left if this is the challenge: https://www.hackerearth.com/spini-java-hiring-challenge/ Don’t discuss problem till its over.

1 Like
• First create a Sieve of Eratosthenes till 10^6 , complexity = O(n log log n)

• Use the sieve to check weather a number is Alphaprime or not

• Create an array storing number of AlphaPrimes till i , for all i<=10^6. complexity = O(N)

• Then you can answer all the queries in constant time by looking up the above created table. complexity = O(1)

I got an AC using this approach

1 Like

Won’t the last part looking up be done through binary search and would be O(log N*) per query where N* is no of alpha primes?

No , we are storing a array of number of Alphaprimes till a given number N . So we could easily query the array by numOfAlphaPrimes[r]-numOfAlphaPrimes[l-1]

Okie, got it thanks

Please explain more on 3rd step…for example if u are supposed to check 1141…then whats the relation of that array with this number

Since the number of queries is very large we cant run a loop from l to r every time (causes TLE) thats why we run a loop from 1 to 10^6 and store the number of Alphaprimes till each element in an array .

Thnx @bhishma

@bhishma
How we will check whether the no. is alpha prime or not.

This is how I implemented.

``````
private static boolean isAlphaPrime(int n)
{

if(!isComposite[n])
return true;
else
{
while(true)
{
if(n < 10)
{
return !isComposite[n];
}
else
{
n = Integer.parseInt(Integer.toString(n).substring(1));
if(!isComposite[n])
return true;
}
}
}

}

``````
//