For every positive integer
n there exists a number having the form of
111...10...000 that is divisible by
n i.e. a decimal number that starts with all
1's and ends with all
0's. This is very easy to prove: if we take a set of
n+1 different numbers in the form of
1's), then at least two of them will give the same remainder after division by
n (as per pigeonhole principle). The difference of these two numbers will be divisible by
n and will have the desired form. Your aim is to write a program that finds this number.
A positive integer.
p in the form of
111...10...000, such that
p ≡ 0 (mod n). If you find more than one - display any of them (doesn't need to be the smallest one).
Your program has to give the answer in a reasonable amount of time. Which means brute-forcing is not permited:
p = 0 while (p != 11..10.00 and p % n != 0) p++
Neither is this:
do p = random_int() while (p != 11..10.00 and p % n != 0)
Iterating through the numbers in the form of
11..10..00 is allowed.
Your program doesn't need to handle an arbitrarily large input - the upper bound is whatever your language's upper bound is.
2: 10 3: 1110 12: 11100 49: 1111111111111111111111111111111111111111110 102: 1111111111111111111111111111111111111111111111110