HackerEarth- Spini Java Hiring Challenge




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]


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


Link to submission : http://pastebin.com/xmTt2NtZ


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


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


This is how I implemented.

	private static boolean isAlphaPrime(int n)

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