Below is my solution for Problem C. Fair and Square
* Still to add method to handle Large Input 2.
Input is taken from a file(C-small-practice.in)
Method 1:
/*
* @author niraj.nijju
*/
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;
}
}
How do you handle Large Input 2?
ReplyDeleteSorry, I didn't handle Large Input 2.
ReplyDeleteI need to learn for such solution and will come up with it.
You can use the biginteger class in java !!...or code it in python as it can handle very large numbers.
ReplyDelete# PYTHON !
x=input()
def c(j):
r=0
t = j;
while t != 0:
r *= 10
r +=t % 10
t /= 10
if j==r:
return 1
else:
return 0
def sqrt(x):
a= 0
if x>=0:
while a*a < x:
a = a + 1
if a*a == x:
return a
else:
return 0
return 0
for i in range(x):
y=raw_input()
y=y.split(' ')
w=int(y[0])
z=int(y[1])
sum=0
for j in range(w,z+1):
if c(j)==1 and sqrt(j) >0 and c(sqrt(j))==1:
sum+=1
print ("Case #"+str(i+1)+": "+str(sum))
The Problem is reducible to 10^7 !! Below is the code for First large dataset !!
ReplyDelete#Elements in the array are palindromes whose square is also a palindrome !
#JAVA
public void run()
{
int arr[]={1,2,3,11,22,101,111,121,202,212,1001,1111,2002,10001,10101,10201,11011,11111,11211,20002,20102,100001,101101,110011,111111,200002,1000001,1001001,1002001,1010101,1011101,1012101,1100011,1101011,1102011,1110111,1111111,2000002,2001002,10000001,10011001,10100101,10111101,11000011,11011011,11100111,11111111,20000002};
int numTests = in.readInt();
for (int testNumber = 0; testNumber < numTests; testNumber++)
{
int result=0;
out.print("Case #" + (testNumber + 1) + ": ");
String a = in.readString();
String b = in.readString();
BigInteger A = new BigInteger(a);
BigInteger B = new BigInteger(b);
for(int i=0;i<arr.length;i++)
{
BigInteger big1 = new BigInteger(Integer.toString(arr[i]));
BigInteger resultpow = big1.multiply(big1);
String string3=resultpow.toString();
if( (resultpow.compareTo(B)==-1 || resultpow.compareTo(B)==0 ) && (resultpow.compareTo(A)==1 || resultpow.compareTo(A)==0) )
result++;
}
out.println(result);
}
out.close();
}