Google Code Jam Problem C. Fair and Square

Below is my solution for Problem C. Fair and Square

Well I qualified for Google Code Jam 2013 with only 60 points.

* Still to add method to handle Large Input 2.

Problem

Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). Apalindrome is just an integer that reads the same backwards and forwards - so 6, 11 and 121 are all palindromes, while 10, 12, 223 and 2244 are not (even though 010=10, we don't consider leading zeroes when determining whether a number is a palindrome).

He recently became interested in squares as well, and formed the definition of a fair and square number - it is a number that is a palindrome and the square of a palindrome at the same time. For instance, 1, 9 and 121 are fair and square (being palindromes and squares, respectively, of 1, 3 and 11), while 16, 22 and 676 are not fair and square: 16 is not a palindrome, 22 is not a square, and while 676 is a palindrome and a square number, it is the square of 26, which is not a palindrome.

Now he wants to search for bigger fair and square numbers. Your task is, given an interval Little John is searching through, to tell him how many fair and square numbers are there in the interval, so he knows when he has found them all.

Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has 1 Small input and 2 Large inputs. Once you have solved the Small input, you will be able to download any of the two Large inputs. As usual, you will be able to retry the Small input (with a time penalty), while you will get only one chance at each of the Large inputs.

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains two integers, A and B - the endpoints of the interval Little John is looking at.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of fair and square numbers greater than or equal toA and smaller than or equal to B.

Limits

Small dataset

1 ≤ T ≤ 100.

1 ≤ A ≤ B ≤ 1000.

First large dataset

1 ≤ T ≤ 10000.

1 ≤ A ≤ B ≤ 10¹⁴.

Second large dataset

1 ≤ T ≤ 1000.

1 ≤ A ≤ B ≤ 10¹⁰⁰.

Sample

Input	Output
3 1 4 10 120 100 1000	Case #1: 2 Case #2: 0 Case #3: 2

Input is taken from a file(C-small-practice.in)

Method 1:

/*

* @author niraj.nijju

*/

package gcj.TwelveThirteen;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;

public class SmallOfFairAndSquare {

public static void main(String [] args){
try{
// System.out.println(Double.MAX_VALUE);
// System.exit(0);

  FileInputStream fstream = new FileInputStream("C-small-practice.in");
  DataInputStream in = new DataInputStream(fstream);
  BufferedReader br = new BufferedReader(new InputStreamReader(in));
  String strLine;
  strLine = br.readLine();
  int T = Integer.valueOf(strLine);
  System.out.println("T: "+T);
  int i=1;
  while ((strLine = br.readLine()) != null)   {
//   System.out.println (strLine);
  String [] str = strLine.split(" ");
  double x = Double.valueOf(str[0].trim() );
  double y = Double.valueOf(str[1].trim() );
  int count= getFairSqur(x,y);
  System.out.println ("Case #"+i++ +": "+count);
  }
  in.close();
}catch (Exception e){//Catch exception if any
  System.err.println("Error: " + e.getMessage());
  e.printStackTrace();
}
}


public static int getFairSqur(double x, double y){
int count=0;
long x1 = (long)Math.ceil(Math.sqrt(x));
long y1 = (long)Math.sqrt(y);

for(long i=x1; i<=y1; i++ ){
if(checkPalindrom(i)){
long sq=i*i;
if(checkPalindrom(sq)){
// System.out.println("("+i+")");
count++;
}
}
}


return count;
}



    public static Boolean checkPalindrom(long n)
    {
     String normal = String.valueOf(n);
    //reverse the letters in string
    int length = normal.length(); //length of string
    StringBuffer result = new StringBuffer(length);
    int i;
    for(i = length - 1; i>=0; i--)
    {
    result.append(normal.charAt(i));
    }
    long r = Long.valueOf(result.toString());

    if(r==n)
     return true;
    return false;
    }


}

Method 2:

/*

* @author niraj.nijju

*/

package gcj.TwelveThirteen;

import java.io.BufferedReader;

import java.io.DataInputStream;

import java.io.FileInputStream;

import java.io.InputStreamReader;

import org.omg.CORBA.INTERNAL;

public class CopyOfFairAndSquare {

public static long [] array = new long[10000010];

public static void main(String [] args){

fillArray();

try{

// System.out.println(Double.MAX_VALUE);

// System.exit(0);

  FileInputStream fstream = new FileInputStream("C-small-practice.in");

  DataInputStream in = new DataInputStream(fstream);

  BufferedReader br = new BufferedReader(new InputStreamReader(in));

  String strLine;

  strLine = br.readLine();

  int T = Integer.valueOf(strLine);

//   System.out.println("T: "+T);

  int i=1;

  while ((strLine = br.readLine()) != null)   {

//   System.out.println (strLine);

  String [] str = strLine.split(" ");

  double x = Double.valueOf(str[0].trim() );

  double y = Double.valueOf(str[1].trim() );

  //int count= getFairSqur(x,y);

  long count=0;

  int xr = (int)Math.sqrt(x);

  int yr = (int)Math.sqrt(y);

  count = array[yr]-array[xr];

  if(xr*xr == (int)x){

  if(checkPalindrom(xr) &&  checkPalindrom(xr*xr)){

  count++;

  }

  }

  

  

  System.out.println ("Case #"+i++ +": "+count);

  }

  in.close();

}catch (Exception e){//Catch exception if any

  System.err.println("Error: " + e.getMessage());

  e.printStackTrace();

}

}

public static void fillArray(){

long count = 0;

for(int i=1;i<array.length;i++){

long j = (long)i;

if(!checkPalindrom(j))

array[i]= count;

else if(!checkPalindrom(j*j))

array[i]= count;

else{

count++;

array[i]= count;

}

}

}

    public static Boolean checkPalindrom(long n)

    {

     String normal = String.valueOf(n);

    //reverse the letters in string

    int length = normal.length(); //length of string

    StringBuffer result = new StringBuffer(length);

    int i;

    for(i = length - 1; i>=0; i--)

    {

    result.append(normal.charAt(i));

    }

    long r=0;

    try{

     r= Long.valueOf(result.toString());

    }catch(Exception e){

     e.printStackTrace();

     System.out.println("i:"+i+"\tr:"+r+"\tn:"+n);

    }

    if(r==n)

     return true;

    return false;

    }

    

    

}