# Competitive Programming: POJ 1426 – Find The Multiple

### Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

### Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

```2
6
19
0
```

### Sample Output

```10
100100100100100100
111111111111111111
```

Solution below . . .

```/*
* 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.
*
*
* 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

//  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))
{
}
}
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();
}
}
```