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?

3
  • The 1's and 0's are in base 10.
    – redDragon
    Feb 8 '15 at 20:47
  • How big numbers are we talking about? My first attempt would be to generate the set of integers to 1,000,000 with this property and then just test manually with integers one by one. Feb 8 '15 at 21:34
  • you can assume that n < 10^5.
    – redDragon
    Feb 8 '15 at 21:55
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.

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.

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.