Algorithm in C - playing with numbers - number with 3 in units place

Question

I came across this question in an interview. Any number with 3 in its units position has at least one multiple containing all ones. For instance, a multiple of 3 is 111, a multiple of 13 is 111111. Given a number ending in 3, I was asked the best method to find its multiple containing all 1's. Now a straightforward approach is possible, where you do not consider space issues but as the number grows, and sometimes even if it doesn't, an int (or a long int at that!) in C cannot hold that multiple. What is the optimal way to implement such an algorithm in C?

Answer 1

UPDATE: Incorporating Ante's observations and making the answer community wiki.

As usual in this type of problems, coding any working brute-force algorithm is relatively easy, but the more math. you do with pencil and paper, the better (faster) algorithm you can get.

Let's use a shorthand notation: let M(i) mean 1111...1 (i ones).

Given a number n (let's say n = 23), you want to find a number m such that M(m) is divisible by n. A straightforward approach is to check 1, 11, 111, 1111, ... until we find a number divisible by n. Note: there might exist a closed-form solution for finding m given n, so this approach is not necessarily optimal.

When iterating over M(1), M(2), M(3), ..., the interesting part is, obviously, how to check whether a given number is divisible by n. You could implement long division, but arbitrary-precision arithmetic is slow. Instead, consider the following:

Assume that you already know, from previous iterations, the value of M(i) mod n. If M(i) mod n = 0, then you're done (M(i) is the answer), so let's assume it's not. You want to find M(i+1) mod n. Since M(i+1) = 10 * M(i) + 1, you can easily calculate M(i+1) mod n, as it's (10 * (M(i) mod n) + 1) mod n. This can be calculated using fixed-precision arithmetic even for large values of n.

Here's a function which calculates the smallest number of ones which are divisible by n (translated to C from Ante's Python answer):

int ones(int n) {
        int i, m = 1;
        /* Loop invariant: m = M(i) mod n, assuming n > 1 */
        for (i = 1; i <= n; i++) {
                if (m == 0)
                        return i;  /* Solution found */
                m = (10*m + 1) % n;
        }
        return -1;  /* No solution */
}

Answer 2

You don't have to consider this question in the 'big number' way. Just take a paper, do the multiplication by hand, and soon you'll find the best answer:)

First, let's consider the units' digit of the result of 3x

 x  0 1 2 3 4 5 6 7 8 9

3x  0 3 6 9 2 5 8 1 4 7

Thus, the relationship is:

what we want 0 1 2 3 4 5 6 7 8 9
 multiplier  0 7 4 1 8 5 2 9 6 3

Second, do the multiplication, and don't save unnecessary numbers. Take 13 for example, to generate a '1', we have to choose the multiplier 7, so

13 * 7 = 91

well, save '9', now what we faces is 9. We have to choose multiplier[(11-9)%10]:

13 * 4 = 52, 52 + 9 = 61

Go on! Save '6'. Choose multiplier[(11-6)%10]

13 * 5 = 65, 65 + 6 = 71

Save '7'. Choose multiplier[(11-7)%10]

13 * 8 = 104, 104 + 7 = 111

Save '11'. Choose multiplier[(11-11)%10]

13 * 0 = 0, 0 + 11 = 11

Save '1'. Choose multiplier[(11-1)%10]

13 * 0 = 0, 0 + 1 = 1

Save '0'. WOW~! When you see '0', the algorithm ends!

Finally, if you print a '1' for one step above, here you will get a '1' string answer.