## Competitive Programming: POJ 1426 – Find The Multiple

18 Apr 2018 / Paul Epps### 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.

### Sample Input

2 6 19 0

### Sample Output

10 100100100100100100 111111111111111111

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
/* * 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://math.stackexchange.com/questions/164986/smallest-multiple-whose-digits-are-only-ones-and-zeros * * 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(); } } |