GCJ 2012 - Recycled Numbers

Posted on April 15, 2012

Below is the problem statement for 'Recycled Numbers' from 'Google Code Jam - 2012':

Problem Statement

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

Let's say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B? Input ----- The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B. 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 recycled pairs (n, m) with A ≤ n < m ≤ B. Limits ------ 1 ≤ T ≤ 50. A and B have the same number of digits. Small dataset ------------- 1 ≤ A ≤ B ≤ 1000. Large dataset ------------- 1 ≤ A ≤ B ≤ 2000000. Sample Input ------------ 4 1 9 10 40 100 500 1111 2222 Sample Output ------------- Case #1: 0 Case #2: 3 Case #3: 156 Case #4: 287

For the above problem, a normal solution works for the small input datasets, but for larger input datasets, a bit of optimization has to be done. Below is the solution for the above problem, in Java.

Blog Categories
The views expressed on this blog are my personal views and do not reflect the views of my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.