Coding Puzzle: Recycled Numbers

(Puzzle from Google Codejam Qualifier Round 2012)

Problem

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 An < mB?

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 An < mB.

Limits

1 ≤ T ≤ 50.
A and B have the same number of digits.

Small dataset

1 ≤ AB ≤ 1000.

Large dataset

1 ≤ AB ≤ 2000000.

Sample

Input Output
4
1 9
10 40
100 500
1111 2222
Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287

Solution:
-Rotate a number (mathematically)
-If number lies between A & B increment total
-Print total/2 (All pairs occur twice)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;

public class RecycledNumbers {
	public static void main(String args[]) throws IOException {
		BufferedReader bfr = new BufferedReader(new FileReader("inputC.txt"));

		Writer output = null;
		File file = new File("outputC.txt");
		output = new BufferedWriter(new FileWriter(file));

		int T = Integer.parseInt(bfr.readLine());
		int i = 0;
		while (i < T) {

			String[] temp = bfr.readLine().split(" ");
			int total = 0;
			int A = Integer.parseInt(temp[0]);
			int B = Integer.parseInt(temp[1]);
			for (int j = A; j <= B; j++) {

				long number = j;
				long start = number;

				int numdigits = (int) Math.log10((double) number);
				int multiplier = (int) Math.pow(10.0, (double) numdigits);

				while (true)
				{
					long r = number % 10;
					number = number / 10;
					number = number + multiplier * r;

					if (number == start)
						break;
					if ((int) number >= A && (int) number <= B) {
						total++;
					}
				}
			}

			output.write("Case #" + (i + 1) + ": " + (total / 2));
			if (i != T - 1) {
				output.write("\n");
			}

			i++;
		}
		output.close();
	}
}

Test Files (Large Dataset)
Input->Input.txt
Output-> Output.txt

Leave a Reply

Your email address will not be published. Required fields are marked *