ONEZERO - Ones and zeros

Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.


Number K of test cases (K is approximately 1000);
in each of the next K lines there is one integer n (1 <= n <= 20000)


For each test case, your program should compute the smallest multiple of the number n consisting only of digits 1 and 0 (beginning with 1).



hide comments
jmr99: 2018-10-16 11:07:39

wow just wow !! *__*

rajhim2: 2018-07-22 14:15:05

If one is using C++ then for numbers like n=19999,19953, etc. the multiples will exceed the limit of int and eventually you will have to use string. You will have to create a separate function for longDivision. If one is using python then it is very easy problem for python users.
For C++ users the approach is like this:
1. Code to generate binary numbers -- this is simple bfs problem.
2. Perform long division.

Last edit: 2018-07-22 14:15:45
oneinchatatime: 2018-06-03 19:19:57

Great problem!!
Weak test cases though :(

codeking123: 2018-03-14 18:29:44

thanks to tarun

tarun2619: 2018-02-24 05:46:21

For optimizing bfs :

sagarstorm: 2018-01-22 15:40:35

Nice problem, lot of things to take care of

yashgulani: 2017-11-07 21:20:34

test cases are weak , there is no test case having n=1 boundary condition . Please improve the test case for this particular question .

aditya930: 2017-10-20 15:47:04

getting WA can someone help wrong answer code is

vishesh197: 2017-10-17 17:11:10

did it using bfs ......but used modular arithmetic for checking took me 5.44sec but AC in first go.Can anybody help me with my implementation....

nadstratosfer: 2017-10-17 10:37:54

If you come here to practice BFS, look elsewhere. It's basically a bruteforce trial division over binary-looking numbers. People raving about smart-sounding acronyms here remind me of binmen calling themselves "environmental officers".

Added by:PaweĊ‚ Dobrzycki
Time limit:8s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:II Polish Olympiad in Informatics, Ist Stage