Apr 24, 2013

Google Code Jam 2013 - Fair And Square

The next problem I attempted after solving Tic-Tac-Toe-Tomek was Fair and Square. A number is determined to be fair and square if it is both a palindrome and has an integral square root. 1, 4, 9, and 121 are fair and square but 676 is not. The submission of the small dataset officially qualified me for Round 1.

There were three datasets: a small and two large. I was able to quickly attack the small with the following snippet of code. Because the range was fairly small (1 >= B >= 1000), it's sufficient to use a brute force solution. You might have noticed that I used BigInteger instead of Integer in the code. At first glance, this seems like overkill. You can certainly do the same thing using ints and Math.pow or Math.sqrt. The problem with that approach is that both of them require doubles so you would have to cast to a double and back. The power convenience function returns a Number object there's no casting needed. After getting the square root, I checked if both were palindromes.

  for (i in 1..n) {
    int start = scanner.nextInt()
    int end = scanner.nextInt()
    int count = 0
    for (j in start..end) {
      def x = new BigInteger(""+j)
      // small only
      def sq = x.power(0.5)
      def isSq = sq.toString().indexOf('.')
      if (isSq == -1) {
          // is square
          if (x.toString().equals(x.toString().reverse()) &&
              sq.toString().equals(sq.toString().reverse())) {
              println x
              count++
          }
      }
    }

    text += "Case #${i}: ${count}\n"
  }

The large datasets were a special case in that you were only allowed to attempt them once. Rather naively, I tried the above code against the smaller of the two large datasets (1 >= B >= 10^14) and it timed out. I wasn't able to get something working for the largest dataset (1 >= B>= 10^100). The key to the larger datasets seemed to be either pre-generating the list of fair and squares either by running a brute force algorithm before retrieving the large dataset or by observing the patterns and generating them on the fly.

Further Optimizations

Returning back to the knowledge that BigInteger.power returns a Number, for the small dataset only, I could have tested if the square root was an Integer. If that test fails, there's no reason to do 4 costly String initializations when that state isn't possible. This strategy would fair better than the above code, which would start to break once the JVM switched to exponential notation.