0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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"

$\endgroup$
  • $\begingroup$ I have edited the question. I got your point that why we can ignore y. I have one more doubt How can we say that the smallest result will be obtained via x only? Maybe y can give result faster than x.. $\endgroup$ – shiwang Jun 14 '18 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.