2

To design an algorithm that will output the smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0 and x > 0..... For example:

2 divides 10

3 divides 111

4 divides 100

5 divides 10

6 divides 1110

7 divides 1001 and so on.

The 1's and 0's are in base 10 representation.

I know that we can solve this using the pigeon hole principle but in this problem we are interested in the smallest number.

I was thinking of using a DP approach similar to a subset sum problem where the set contains 1, 10, 100, 1000 and so on. I am not completely clear about how to formulate the recurrence relation for this problem. Can someone give some insight?

redDragon
  • 95
  • 1
  • 7

2 Answers2

2

Just an outline of thought.

To me, it seems bruteforce and streetsmart will beat any theoretical approach.

Example #1

If N contains a factor of 2 up to multiplicities K, then you can deduce that the lowest digits of X will have to contain at least K consecutive zeroes, because only consecutive zeroes in the lowest digits can provide factors of 2. And so on. Doesn't seem to involve any theories.

Example #2

Another streetsmart is the divisibility by 9 of decimal numbers judged by the sum of decimal digits. (More precisely it's the property of the modulo by 9. Divisibility refers to modulo giving zero. Divisibility by 3 is a simple corollary derived from the modulo by 9.) Note that by using "modulo", it is apply it to any numbers, say 13, by filtering the candidates of X with the requirement that mod(X_candidate, 9) == mod(13, 9) == 4. The requirement is necessary but not sufficient, but it helps cutting down the number of cases needed by the bruteforce.

rwong
  • 16,695
  • 3
  • 33
  • 81
1

Dynamic programming is much better than brute force plus a few heuristics.

Try to determine the minimum number of digits so that some 0-1 integer is a mod n.

For example, you could make a dictionary whose keys will be integers mod n, and whose values are the least number of digits so that there is some 0-1 integer equal to the key mod n. Start with (0,0). For each k, compute 10^(k-1) mod n, and go through every key a to see whether b=a+10^(k-1) mod n is a key yet. If not, add (b,k) to the dictionary. If b is 0, then we have found the number of digits needed.

Once you have the number of digits needed for each reduction of a number with at most k digits, you can determine the least number recursively. If you reach a mod n with k digits, then the least 0-1 number congruent to a mod n is 10^(k-1) plus the least 0-1 number congruent to a-10^(k-1) mod n.

This takes O(n^2) time, since for each k, you generate at least one new congruence class mod n while adding 10^(k-1) to at most n old congruence classes. Perhaps there is some memoization that would speed up the cases where a small number of congruence classes are generated at a time, such as when a small power of 10 is 1 mod n.

Douglas Zare
  • 136
  • 2