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

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 i开发者_JAVA技巧n 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?

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 */
}

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.

Like Bolo's solution with simpler equality M(i+1) = 10*M(i) + 1. Here is python version:

def ones( n ):
  i = m = 1
  while i <= n:
    if m == 0:
      return i
    m = ( ( 10 * m ) + 1 ) % n
    i += 1
  return None

The multiple of 23 is 1111111111111111111111

#include <stdio.h>

int
main () {
        unsigned int ones = 1;
        double result, by = 23, dividend = 1;
        while (dividend) {
            result = dividend / by;
                if (result < 1) {
                    dividend = dividend * 10 + 1;
                        ++ones;
                } else {
                    dividend -= by * (int)result;
                }
        }
        while (ones--) {
            printf("1");
        }
        printf("\n");
    return 0;
}

In case, someone is looking for a solution in Java:

public static void main(String[] args) {

    int input = 55333;
    int minAllOnesNum = 1;
    int nextAllOnesNum= minAllOnesNum;  

    int numberof1s=1;
    int count = 0;
    while(true)
    {
        count++;

        if(nextAllOnesNum%input == 0 ) 
        {
            break;  
        }

        nextAllOnesNum = nextAllOnesNum*10 + 1;

        if(nextAllOnesNum>=input) {
            nextAllOnesNum%=input;
        }
        numberof1s++;
    }


    System.out.println("count : " + count);

    for(int i=1; i<=numberof1s; i++) {
        System.out.print("1");
    }
}