Massive Algorithms: UVa 10127: Ones

UVa 10127: Ones | MathBlog
Given any integer 0 ≤ n ≤ 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1’s. How many digits are in the smallest such a multiple of n?

Input
A file of integers at one integer per line.

Output
Each output line gives the smallest integer x > 0 such ∑x−1
i=0 1 × 10i = a × b, where a is the corresponding input integer, and b is an integer greater that p = than zero.

Sample Input
3
7
9901

Sample Output
3
6
12

public static int getDigitCount(int n) {

    // loop through multiples of n

    for (int i = n; ; i += n) {

        // create a copy of i

        int tmp = i;

        // the number of digits in i

        int digitCount = 0;

        // whether i only consists of ones

        boolean ok = true;

        // while there are digits left in tmp

        while (tmp > 0) {

            // if the current digit in tmp is not a one

            if (tmp % 10 != 1) {

                // then i is not an answer

                ok = false;

                break;

}

            // the current digit is a one, so we chop it off

            // and increment the digit count

            tmp = tmp / 10;

            digitCount++;

}

        // if i consists only of ones

        if (ok) {

            // then i is a solution, so we return the digit count

            return digitCount;

}

}

}

The correct output for the last test case is $12$ . What does that mean? It means that the smallest multiple of $9901$ that consists only of ones is $12$ digits long. Now we realize that we are using a signed 32 bit integer (aka int in Java and similar programming languages), and a signed 32 bit integer cannot contain integers greater than $2^{31} - 1$ , which is about $10^9$ , but the correct multiple is about $10^{12}$ . So what can we do? Well, we could use a 64 bit integer (aka long), but you would later find out that it won’t work for this problem.

We have chosen to go the smart way instead, which is to throw out our current solution and try to find a better one.

Let’s try thinking about our previous solution, but in reverse mode. We generated multiples of $n$ and checked if they consisted only of ones. But what about doing the opposite? Generate numbers that consist only of ones, and check if they are a multiple of $n$ . Sounds like a good plan to me!

But how do we generate numbers that consist only of ones? It’s actually pretty easy… The first number is $1$ , the next number is $1 \times 10 1 = 11$ , then $11 \times 10 1 = 111$ , and so on. Or in general, $\mathrm{last} \times 10 1 = \mathrm{next}$ .

public static int getDigitCount(int n) {

    // the first number to check is 1

    int current = 1;

    // 1 has a digit count of 1

    int digitCount = 1;

    // while n is not divisible by the current number

    while (current % n != 0) {

        // we add one 1 to the end of current

        current = current * 10 + 1;

        // and increment the digit count

        digitCount++;

}

    return digitCount;

}

$\displaystyle (a b) \textrm{ \% } m = ((a \textrm{ \% } m) (b \textrm{ \% } m)) \textrm{ \% } m$

$\displaystyle (a \times b) \textrm{ \% } m = ((a \textrm{ \% } m) \times (b \textrm{ \% } m)) \textrm{ \% } m$

$\displaystyle (a - b) \textrm{ \% } m = ((a \textrm{ \% } m) - (b \textrm{ \% } m)) \textrm{ \% } m$

This way we never actually work with the full result, but rather the full result modulo $n$ (which is at most $n - 1$ ).

public static int getDigitCount(int n) {

    // the first number to check is 1

    int current = 1;

    // 1 has a digit count of 1

    int digitCount = 1;

    // while current is not divisible by n

    while (current % n != 0) {

        // add one 1 to the end of current,

        // and do it modulo n

        current = (current * 10 + 1) % n;

        // and increment the digit count

        digitCount++;

}

    return digitCount;

}

Read full article from UVa 10127: Ones | MathBlog

UVa 10127: Ones | MathBlog

Labels

Popular Posts