## Concatenate N N Times

### May 10, 2016

A number like 7777777 consists of the number 7 concatenated to itself 7 times. A number like 121212121212121212121212 consists of the number 12 concatenated to itself 12 times.

Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

Tried this in perl – as perl has the built in operator… the concatenation is about 40% faster then the numeric method – and works for larger values of n….

Simple iterative solution O(n):

Notice that it performs n multiplications and n additions that quickly enough are bignum operations.

This is typically an operation that can be reduced to O(logn), by noticing that when n is even:

and when n is odd:

Therefore we can write:

I doubt James tested his perl string version on non-single digit numbers; going thru strings is 6 times slower than the iterative arithmetic solution, and 1000 times slower than the dichotomy arithmetic solution:

I meant the factors for 1234.

Converting the number to a string is O(logn) divisions; concatenating the strings can be made O(n^2) memory accesses (the length of the string is n*n=n^2); reading the result is O(n^2) multiplications+additions. Total, the string version is O(n^2) multiplications, while the simple iterative is only O(n) multiplication and the dichotomic one is O(logn) multiplications.

Here’s a couple of Python solutions, one short and snappy using strings, one using bignum arithmetic. The string solution is faster for smaller n, but with bignums winning for larger (>200) n – by n = 100000, bignums are 15 times faster, probably converting megabyte strings to ints doesn’t scale well.

Here’s a solution in Java that iteratively reads an additional character until the parsed integer times its string length equals the length of the entire string. I assumed inputs are valid (e.g., 333 is valid, 332 is not but my program would also return 3 for that). At return time, I could check for validity but didn’t bother.

Output:

Output:

> “Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say).”

I just looked at the solution and skimmed some other solutions. I think I interpreted the task slightly differently than others. It seems like the typical interpretation is that the input is N, and the output is N concatenated N times. I thought the input was N concatenated N times, and the output was N. I re-read the task and think it can be interpreted either way (its ambiguous, like many natural language sentences).

Building the output in an array of chars is wicked fast. The following – in c# – completes in 1 millisecond with n = 100000:

A math solution requires approximately 40000 milliseconds for the same n = 100000:

I have two solutions both using python and does substring comparison although numeric comparisons are cool.

First version is kind of greedy approach

Second version uses indexes to compare substrings – it resembles to dynamic programming solutions.

Performance comparison, measured by ipython’s timeit builtin function.

First version seems to do better at first glance

But i suspected that second version would do better when repeated substring becomes much larger, and it indeed did perform better