https://drive.google.com/file/d/0B3RSnegdFaaFLVlmOXpuLVJrQ0U/view?usp=sharing
Hiring Challenge Problem. Any ideas for the solution.
P.S.–>> The “later later later” one Post is this.
https://drive.google.com/file/d/0B3RSnegdFaaFLVlmOXpuLVJrQ0U/view?usp=sharing
Hiring Challenge Problem. Any ideas for the solution.
P.S.–>> The “later later later” one Post is this.
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
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.
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]
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 .
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;
}
}
}
}