PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

Fair and Square Solution: Google codejam 2013 Qual Round

(2 votes, average: 1.00 out of 5)

April 14, 2013 by puzzler Leave a Comment

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the third problem from Qualification Round 2013.

Problem Statement

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 to Aand 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 ≤ 1014.

Second large dataset

1 ≤ T ≤ 1000.
1 ≤ A ≤ B ≤ 10100.

Sample

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

Solution with Java Code and Explanation

This program for first two input sets can be done by getting all the palindromes of digits less than or equal to height range, get the square of each palindrome and if it lies between the range we will check if is it a palindrome or not. This program further can be optimized for memory by not storing palindromes in memory and checking for fair and square formed by it immediately.

NOTE: this program will not execute for the third set as we are working using longs and also even if we take biginteger it will take lot of time to even get the palindromes. This require some more eleminations or pre calculated fair and square numbers in file system.

Here is the Java code for Fair and Square problem in Google codejam Qualification round 2013

package googlecodejam2013;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;

public class LawnMover {

	public boolean isPossible(int[][] pattern, int n, int m){
		for(int i=0; i < n; i++){
			for(int j=0; j < m; j++){
				if(!isNumberPossible(pattern, i, j, n, m, pattern[i][j])){
					return false;
				}
			}
		}
		return true;
	}
	
	private boolean isNumberPossible(int[][] pattern, int row, int col, int n, int m, int num){
		boolean isColPossible = true;
		boolean isRowPossible = true;
		for(int j=0; j < m; j++){
			if(pattern[row][j] > num){
				isRowPossible = false;
				break;
			}
		}
		
		for(int i= 0; i < n; i++){
			if(pattern[i][col] > num){
				isColPossible =  false;
				break;
			}
		}
		return isColPossible || isRowPossible;
	}
	
	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("C:\\Users\\AvinashS\\Desktop\\google\\lawnmover\\large.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;
	
			File file = new File("C:\\Users\\AvinashS\\Desktop\\google\\lawnmover\\large.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				ArrayList<Integer> nAndM = getIntegerList(bufReader.readLine());
				;
				String output = (new LawnMover().isPossible(getLawnPattern(bufReader, nAndM.get(0), nAndM.get(1)), nAndM.get(0), nAndM.get(1)) ? "YES":"NO");
				writer.write("Case #" + count + ": " + output+"\n");
				System.out.println("Case #" + count + ": " + output);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static int[][] getLawnPattern(BufferedReader bufReader, int n, int m) throws IOException{
		int[][] pattern = new int[n][m];
		
		for(int i =0; i <n; i++){
			ArrayList<Integer> rowList = getIntegerList(bufReader.readLine());
			
			for(int j=0; j<m;j++){
				pattern[i][j] = rowList.get(j);
			}
		}
		return pattern;
	}
	
	private static ArrayList<Integer> getIntegerList(String s) {
		ArrayList<Integer> intList = new ArrayList<Integer>();
		String[] strArr = s.split(" ");
		for (String str : strArr) {
			intList.add(Integer.parseInt(str.trim()));
		}
		return intList;
	}
	
}
  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Facebook
Next Puzzle
Bullseye Solution: Google codejam 2013 Round 1A

Checkout more Interview Questions Tags: Difficult, Google codejam, Interview, Java, Solved Puzzles

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Swap two integer variables
  • Consonants Solution: Google codejam 2013 Round 1C
  • Spinning Disc Direction Puzzle
  • Beautiful Strings solution: Facebook hacker Cup 2013 Qual Round
  • RoboElection solution: Facebook hacker cup 2013 Round 2
  • Balanced Smileys solution: Facebook hacker Cup 2013 Qual Round
  • Three blue and two red hats puzzle
  • Security problem solution: Facebook hacker cup 2013 Round 1
  • Charging Chaos Solution – Google CodeJam
  • Dead Pixels solution: Facebook hacker cup 2013 Round 1

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous