We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Alice and Bob's Silly Game
  5. Discussions

Alice and Bob's Silly Game

  • vivekGhosh
     + 1 comment

    I optimized your code a little bit further to actually remember the results from all previous iterations to avoid rechecking of already checked numbers.

    import java.util.*;
class pgame
{
	private NavigableMap<Integer,Integer> map;
	private int max;
	private int count;
	
	public pgame()
	{
		map = new TreeMap<Integer,Integer>();
		max = 0;
		count = 0;
		map.put(0,0);
	}
	
	private boolean isPrime(int n)
	{
        if(n<=1)
            return false;
		else if(n==2 || n==3)
			return true;
		else if(n%2==0 || n%3==0)
			return false;
		else
		{
			int i = 5,w = 2;
			while(i*i<=n)
			{
				if(n%i==0)
					return false;
				i+=w;
				w = 6-w;
			}
			return true;
		}
	}
	
	private int getPrimeCount(int n)
	{
        if(n<=max)
		    return map.get(map.floorKey(n));
        else
		{
            int i;
			for(i = max+1;i<=n;i++)
			{
				if(isPrime(i))
				{
                    count+=1;
					map.put(i,count);
                }
            }
			max = n;
            return count;
		}
	}
	
	public String getWinner(int n)
	{
        if(getPrimeCount(n)%2==0)
			return "Bob";
		else
			return "Alice";
	}
	
	public static void main(String args[])
	{
		try
		{
			Scanner s = new Scanner(System.in);
			int g = s.nextInt();
			int i;
			pgame temp = new pgame();
			for(i = 1;i<=g;i++)
				System.out.println(temp.getWinner(s.nextInt()));
		}
		catch(Exception e)
		{
			System.out.println("Exception caught - "+e);
		}
	}
}