Find the smallest binary digit multiple of given number

Question

I was reading an article on Find the smallest binary digit multiple of given number. The problem is - We are given a decimal number N, we need to find the smallest multiple of N which is binary digit number.

There is an optimization done i.e. if a string with same mod value is previously occurred we won’t push this new string into our queue. The explanation given is-

Let x and y be strings, which gives same modular value with n. Let x be the smaller one. let z be another string which when appended to y gives us a number divisible by N. If so, then we can also append this string to x, which is smaller than y, and still get a number divisible by n. So we can safely ignore y, as the smallest result will be obtained via x only.

How can we say that, we can also append this string to x, which is smaller than y, and still get a number divisible by n ?

And how can we say that the smallest result will be obtained via x only?

Answer 1

No idea where you got that 9 from, in the last line of the question.

Having said that, You have to know that "concatenating" numbers is equivalent to multiplying the first number by a power of 10, followed by adding the second number. E.g. 42|7 = (42*10)+7.

Now obviously 42 is divisible by 6, but therefore so is 420. Furthermore, 42 mod 5 = 2, therefore 420 mod 5 = 20 mod 5. "42 is divisible by 6" in fact means "42 mod 6 = 0"