HackerEarth- Spini Java Hiring Challenge

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.

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

Still 2 hours are left if this is the challenge: Spini Java Hiring Challenge Don’t discuss problem till its over.

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

Link to submission : Hackerearth Alphaprime problem - Pastebin.com

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;
				}
			}			
		}

	}