Counting Sheep

Introduction

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

Bleatrix must start with N and must always name (i + 1) × N directly after i × N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

N = 1692. Now she has seen the digits 1, 2, 6, and 9. 2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9. 3N = 5076. Now she has seen all ten digits, and falls asleep. What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

Solutions

Idea

After some thinking, it was assumed that the only N for which all digits wouldn't show up would be N = 0. As a result, it was only necessary to have a special check for n==0, and print "INSOMNIA". In all other cases, Bleatrix would end up falling asleep - I just had to find out when. I started by adding the digits 0-9 to a hashset for checking if they had been seen - a boolean array would've been just as effective, but a HashSet made some actions easier because of its built in functions (contains, isEmpty, etc). I then created a while loop where I repetitively multiplied by 1, 2, etc ... until all the digits 0-9 had all been seen. When a digit was seen, I removed it from the hashset, and broke out of the while loop when the set was empty.

Runtime

Adding and checking the HashSet was done in constant time since there were only 9 digits. However, multiplying the number until all digits were seen appeared to be largely based on the properties of the number itself. For example, the number 1 only had to be multiplied up to 10, while the number 2 had to be multiplied up to 45.

Code

Solution - Java

import java.util.*;
import java.io.*;
import java.io.FileReader;
import java.io.File;
public class codejam1 {
	public static void main(String[] args) throws FileNotFoundException, IOException{
		Scanner sc = new Scanner(new FileReader("src/A-large.in"));
		int numInputs = sc.nextInt();
		PrintWriter writer = new PrintWriter("output.txt", "UTF-8");
		for (int i = 1; i <= numInputs; i++){
			writer.println("Case #" + i + ": " + solveProblem(sc.nextInt()));
		}
		writer.close();
		sc.close();
	}
	
	public static String solveProblem(int n){
		if (n==0){
			return "INSOMNIA";
		}
		HashSet<Integer> seenInts = new HashSet<Integer>();
		for (int i = 0; i < 10; i++){
			seenInts.add(i);
		}
		
		int i = 0;
		while (!seenInts.isEmpty()){
			i++;
			int num = n * i;
			while (num > 0){
				if (seenInts.contains(num % 10)){
					seenInts.remove(num % 10);
				}
				num = num / 10;
			}
		}
		return Integer.toString(i*n);
	}
}