HackerEarth- Spini Java Hiring Challenge

java

#1

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.


#2
  • 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


#3

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.


#4

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?


#5

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]


#6

Okie, got it thanks


#7

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


#8

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


#9

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 .


#10

Thnx @bhishma


#11

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


#12

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

	}