Dashboard - Qualification Round 2013 - Google Code Jam
Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). A palindrome 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.
Output
http://arxoclay.blogspot.com/2013/04/google-code-jam-fair-and-square.html
(1) My method involved finding all the 'fair and square' numbers in the range my program would expect.
(2) At that point, given a range for an individual test case, I would just have to do a membership check on the precomputed list I had generated in (1).
}
FairNSquareLarge.java:
http://toughprogramming.blogspot.com/2013/04/code-jam-2013-qualification-round.html
https://jameswilliams.be/blog/2013/04/24/Google-Code-Jam-2013-Fair-And-Square.html
https://github.com/vibneiro/googleJam2013/blob/master/FairNSquare.java
http://google-tale.blogspot.com/2013/04/gcj-2013-fair-and-square.html
to-do: http://tavianator.com/fair-and-square-or-how-to-count-to-a-googol/
Read full article from Dashboard - Qualification Round 2013 - Google Code Jam
Little John likes palindromes, and thinks them to be fair (which is a fancy word for nice). A palindrome 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.
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.
Input3
1 4
10 120
100 1000Output
Case #1: 2
Case #2: 0
Case #3: 2http://arxoclay.blogspot.com/2013/04/google-code-jam-fair-and-square.html
(1) My method involved finding all the 'fair and square' numbers in the range my program would expect.
(2) At that point, given a range for an individual test case, I would just have to do a membership check on the precomputed list I had generated in (1).
public static boolean isPalindrome(long number)
{
char[] numberString = Long.toString(number).toCharArray();
int lengthNumberString = numberString.length;
for (int i = 0; i < lengthNumberString/2; i++)
{
if (numberString[i] != numberString[lengthNumberString - (i + 1)])
{
return false;
}
}
return true;
}
public static ArrayList<Long> fairAndSquare(long maximum)
{
ArrayList <Long> fairAndSquares = new ArrayList<Long>();
for (long i = 1; i < maximum; i++)
{
if (isPalindrome(i))
{
long product = i * i;
if (isPalindrome(product))
{
fairAndSquares.add(product);
}
}
}
return fairAndSquares;
}
public static void main(String[] args) throws IOException {
ArrayList<Long> results = fairAndSquare(10000000); // Will give me products upto 10^14
long startPoint = Long.parseLong(line.split(" ")[0]);
long finishPoint = Long.parseLong(line.split(" ")[1]);
long totalCount = 0;
for(int i = 0; i < results.size(); i++)
{
if (results.get(i) >= startPoint && results.get(i) <= finishPoint)
{
totalCount ++;
}
}
out.write("Case #" + Integer.toString(caseCounter) + ": " + Long.toString(totalCount) + "\n");
FairNSquareLarge.java:
| private static boolean isPalindrome(BigInteger num) { BigInteger reversed = BigInteger.ZERO; | |
| BigInteger n = num; | |
| while (n.compareTo(BigInteger.ZERO) > 0) { | |
| reversed = reversed.multiply(BigInteger.valueOf(10)).add(n.mod(BigInteger.valueOf(10))); | |
| n = n.divide(BigInteger.valueOf(10)); | |
| } | |
| return num.compareTo(reversed) == 0; | |
| } | |
| private static BigInteger sqrt(BigInteger n) { | |
| BigInteger a = BigInteger.ONE; | |
| BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString()); | |
| while(b.compareTo(a) >= 0) { | |
| BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString()); | |
| if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE); | |
| else a = mid.add(BigInteger.ONE); | |
| } | |
| return a.subtract(BigInteger.ONE); | |
| } | |
| private void solve(Scanner sc, PrintWriter pw) { | |
| BigInteger a = sc.nextBigInteger(); | |
| BigInteger b = sc.nextBigInteger(); | |
| BigInteger number = a; | |
| long count = 0; | |
| while(number.compareTo(b) <= 0) { | |
| if(isPalindrome(number)) { | |
| BigInteger d = sqrt(number); | |
| if(d.multiply(d).compareTo(number) == 0 && isPalindrome(d)) { | |
| count++; | |
| } | |
| } | |
| number = number.add(BigInteger.ONE); | |
| System.out.println(number.toString()); | |
| } | |
| pw.println(count); | |
| } |
http://toughprogramming.blogspot.com/2013/04/code-jam-2013-qualification-round.html
https://jameswilliams.be/blog/2013/04/24/Google-Code-Jam-2013-Fair-And-Square.html
https://github.com/vibneiro/googleJam2013/blob/master/FairNSquare.java
http://google-tale.blogspot.com/2013/04/gcj-2013-fair-and-square.html
to-do: http://tavianator.com/fair-and-square-or-how-to-count-to-a-googol/
Read full article from Dashboard - Qualification Round 2013 - Google Code Jam
