UVA 10127 Ones Solution

Problem 10127 at UVa Online Judge, Ones, is a neat little problem. We are given an integer and are asked to find its smallest multiple that consists only of ones. More specifically, we are asked for the number of ones in that multiple.

Interpretation

We are given an integer  that is neither divisible by  nor . We have to find the smallest multiple of  that consists entirely of ones. For example, when ,  is the smallest multiple of  that consists only of ones. For this problem, we only need the digit count of that multiple, which in the case of  is  (because  has  digits).

Implementation

Let’s just dive right in. Our main method is very plain and looks like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public static void main(String[] args) throws Exception {     Scanner in = new Scanner(System.in);     PrintWriter out = new PrintWriter(System.out, true);       // while there are still numbers to check     while (in.hasNextInt()) {           // read the number         int n = in.nextInt();           // print the solution         out.println(getDigitCount(n));     } }

All the work is being done in the getDigitCount method. Let’s implement it now. We’ll start off by creating a brute-force solution that checks all multiples of . If the current multiple only consists of ones, we’ve found our solution, if not, we need to keep looking. We could convert the multiple to a string to check if it only consists of ones, but we can also walk through each digit of the number by using the modulo operator and integer division.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

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;         }     } }

Now we have a simple (maybe too simple) solution. A very good rule is to test your solution on the given test input before you even consider submitting it. Let’s follow our rule and test our solution with the given input, which in this case is:

1 2 3

3 7 9901

And the correct output is:

1 2 3

3 6 12

Our current solution returns the following incorrect output:

1 2 3

3 6 0

Why did that happen? Let’s think about it for a minute. The correct output for the last test case is . What does that mean? It means that the smallest multiple of  that consists only of ones is  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 , which is about , but the correct multiple is about . 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  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 . 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 , the next number is , then , and so on. Or in general, .

Our new and shiny getDigitCount now looks like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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; }

But we still have the same problem! We are trying to contain the whole result inside a 32 bit integer. But our work on the new method was not a waste, since we can modify it to get a correct solution, but how? Let’s check what we’re actually doing with the current variable (the integer that contains the sequence of ones). We are doing one modulo operation (current % n) and a little bit of addition/multiplication (current = current * 10 + 1). Currently, we are taking the modulo only when we’re checking if current is divisible by . But due to how the modulo operator works, it doesn’t actually matter when we apply it. The following rules should give you an idea of what I mean:

Note that the rule about subtraction may need special care in some programming languages, but we’re not using subtraction here.

These rules also work over different operators, as long as we are always working with the same . With this in mind, we can complete our solution by adding an extra modulo operator when we append a one to current. This way we never actually work with the full result, but rather the full result modulo  (which is at most ). This method can also be thought of as long division.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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; }

Now we finally have a correct solution, which also of course produces the correct output for the given test data. The algorithm runs in time proportional to the number of digits in , which is good enough.

Solution in c++:
///**********ALLAH IS ALMIGHTY************///
///AH Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh

#include<iostream>

using namespace std;

int main()

{

int n,r,c,i;

while(cin>>n)

{

    i=1;

    c=1;

    while(c%n!=0)

    {

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

        i++;

    }

    cout<<i<<endl;

}

}