Competitive Programming: POJ 1426 – Find The Multiple

/*
 * There are at least 3 ways to solve this:
 * 
 * 1. NUMERICAL METHODS
 * 
 * I found several links to numerical methods and couldn't 
 * understand any of them. Here's a sample:
 * 
 * https://bit.ly/2vSpGbc
 * 
 * 2. CHEAT
 * 
 * Input is guaranteed to be no more than 200, and results 
 * have been computed for far more numbers than that 
 * (see http://oeis.org/A004290/b004290.txt). 
 * Put the answers in a hash table and just look them up.
 * 
 * 3. BREADTH-FIRST SEARCH (BFS)
 * 
 * Every node of the search tree will be a binary digit 
 * number. For each number x, the next-level nodes will be 
 * x0 and x1 (x concatenated with 0 and 1).
 * 
 * We start by adding 1 to the queue, which will then 
 * add 10 and 11 and so on. After taking a number from 
 * the queue, we’ll check whether the number is a multiple 
 * of the given number or not. If yes, we have our answer.
 * 
 * Optimization: we're using a set for mod values. If a 
 * number has a previously seen mod value, we don’t add 
 * this new number to the queue.  Explanation: Let 
* x and y be numbers that give the same value mod N. 
 * Let x < y. Let z be another number which, when appended 
 * to y gives a number divisible by N. Then we can also 
 * append this number to x and get a number divisible by N. 
 * So we can safely ignore y.
 * 
 * NOTE: The sample outputs given for inputs 6 and 19 are 
 * "acceptable" but much smaller answers are available. 
 * 
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	// returns smallest multiple which has
	// only 1s and 0s
	static long getMinimumMultiple(int N)
	{
		Deque<Long> q = new ArrayDeque<Long>();
		Set<Long> visit = new HashSet<Long>();
	 
	    long t = 1;
	 
	    //  starting with 1 in queue
	    q.add(t);
	 
	    //  loop while queue is not empty
	    while (!q.isEmpty())
	    {
	        // Take the first number from queue.
	        t = q.pop();
	 
	        // Find remainder of t with respect to N.
	        long rem = t % N;
	 
	        // if remainder is 0 then we have
	        // found our solution
	        if (rem == 0)
	            return t;
	 
	        // If this remainder is not previously seen,
	        // then add t + '0' and t + '1' to queue
	        else if(!visit.contains(rem))
	        {
	            visit.add(rem);
	            q.add(t * 10);
	            q.add(t * 10 + 1);
	        }
	    }
	    return -1; //something went wrong
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		while (N != 0) {
			System.out.println(getMinimumMultiple(N));
			N = sc.nextInt();
		}
		
		sc.close();
	}
}