UVa 10127: Ones

UVa 10127: Ones

Written by on 16 May 2012

Topics: UVa Online Judge

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:

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.

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:

3
7
9901

And the correct output is:

3
6
12

Our current solution returns the following incorrect output:

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:

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.

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.

Taking it further

Here comes a little extra for those of you who are interested.

I was sure that there was a better way to solve the problem. Now that I had a working solution, I modified it to print out a table of the number, the answer for that particular number, and the prime factorization of the number (I had a feeling it had something to do with the problem).

1		1		1^1
3		3		3^1
7		6		7^1
9		9		3^2
11		2		11^1
13		6		13^1
17		16		17^1
19		18		19^1
21		6		3^1 * 7^1
23		22		23^1
27		27		3^3
29		28		29^1
31		15		31^1
33		6		3^1 * 11^1
37		3		37^1
39		6		3^1 * 13^1
41		5		41^1
43		21		43^1
47		46		47^1
49		42		7^2
51		48		3^1 * 17^1
53		13		53^1
57		18		3^1 * 19^1
59		58		59^1
61		60		61^1
63		18		3^2 * 7^1
67		33		67^1
69		66		3^1 * 23^1
71		35		71^1
73		8		73^1
77		6		7^1 * 11^1
79		13		79^1
81		81		3^4
83		41		83^1
87		84		3^1 * 29^1
89		44		89^1
91		6		7^1 * 13^1
93		15		3^1 * 31^1
97		96		97^1
99		18		3^2 * 11^1
...

What immediately caught my attention were the numbers which had an answer which was one lower than the number itself. These numbers were:

I did a quick search on oeis and found that for each of the number , had a repetition length of . Now I got curious and added another column before the prime factorization which was the repetition length of . Now the table looked like:

1		1		1		1^1
3		3		1		3^1
7		6		6		7^1
9		9		1		3^2
11		2		2		11^1
13		6		6		13^1
17		16		16		17^1
19		18		18		19^1
21		6		6		3^1 * 7^1
23		22		22		23^1
27		27		3		3^3
29		28		28		29^1
31		15		15		31^1
33		6		2		3^1 * 11^1
37		3		3		37^1
39		6		6		3^1 * 13^1
41		5		5		41^1
43		21		21		43^1
47		46		46		47^1
49		42		42		7^2
51		48		16		3^1 * 17^1
53		13		13		53^1
57		18		18		3^1 * 19^1
59		58		58		59^1
61		60		60		61^1
63		18		6		3^2 * 7^1
67		33		33		67^1
69		66		22		3^1 * 23^1
71		35		35		71^1
73		8		8		73^1
77		6		6		7^1 * 11^1
79		13		13		79^1
81		81		9		3^4
83		41		41		83^1
87		84		28		3^1 * 29^1
89		44		44		89^1
91		6		6		7^1 * 13^1
93		15		15		3^1 * 31^1
97		96		96		97^1
99		18		2		3^2 * 11^1
...

Some of the values were the same, and there definitely seemed to be a connection. I investigated patterns and gathered information from Wikipedia, and after a while I came up with the following:

The function returns the digit count of the smallest multiple of that consists only of ones.


, where is a prime, has to be calculated manually with the same method as in our solution above.
(where is a prime and )
(where is a prime and is the least common multiple function)

With these observations, we only have to calculate the digit count manually for primes. If the function is implemented as an array (like I did), we can just manually fill it in which avoids recomputations. Although it was a lot of fun deriving these formulas, I have some bad news for you. Even an efficient C++ implementation of this method is slower than a C++ implementation of our previous solution (according to the online judge). But still, I presented you with this method both for more fun, and also in hope that somebody might derive an even faster method from this one. I’ve also included a not-so optimized version of this method in the complete source code below.

Conclusion

We started off with a slow brute-force method that didn’t even work, but with some clever observations we managed to implement a good solution. I also showed you the interesting results of an attempt I made to make an even faster solution, which unfortunately turned out to be slower (but would still get an Accepted verdict).

The blog image was taken by duncan who shared it under the creative commons license.

You can take a look at the complete source code here.
So what do you think? Did/would you solve it differently? Leave a comment and let us know.

3 Comments For This Post I'd Love to Hear Yours!

  1. Nicely explained!
    Isn’t it fascinating that almost behind every problem somewhere there are the prime numbers? :-)

  2. Bjarki Ágúst says:

    Thanks! I appreciate that.
    But yes, it is amazing how often you stumble upon prime numbers, often in seemingly unrelated problems.

    Nice website by the way. I’ve had my share of fun with expression trees and symbolic differentiation. :)

  3. riham says:

    thnx bro , its helpful.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.