UVa 10706. Number Sequence with F#

This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section.


This is a straight-forward problem, which however, requires careful introspection. Our objective is to write a program that compute the value of a sequence , which is comprised of the number groups . Each consists of positive integers written one after another and thus, the first digits of are —


It is imperative to note that, the value of has the following range . Realize that, the maximum value of is indeed Int32.MaxValue. In the provided test cases, the values of are stated. We simply have to compute ; therefore, we are required to write a function that has following signature: .  That is —

f: 10 --> S.[10] = 4
f: 8  --> S.[8]  = 2
f: 3  --> S.[3]  = 2

Note also that the maximum number of test cases is 25. Question for the reader: What is the maximum possible value of for the specified sequence , which is constituted of  ?

We hope that by this time, it is clear where we are headed towards. In next section, we outline an algorithm to solve this problem. But, before moving further, we would like to recommend you to try to solve it yourselves first and then, read the rest of the post. By the way, we believe that the solution that we have presented next can be further optimized (or, even a better solution can be derived). We highly welcome your feedback regarding this.


Recall that, is constituted of number groups . In order to identify the digit located at the position of , we first determine the number group   that digit is associated with and then, we figure out the    digit from .

To do so, we first compute the length of each number group . Consider the number group till


As mentioned, this sequence is basically constituted of  as shown below (with their respective lengths).

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 3
1 2 3 4              --> 4
1 2 3 4 5            --> 5
1 2 3 4 5 6          --> 6
1 2 3 4 5 6 7        --> 7
1 2 3 4 5 6 7 8      --> 8
1 2 3 4 5 6 7 8 9    --> 9
1 2 3 4 5 6 7 8 9 10 --> 11

It implies that the length of can be computed from the length of as shown below.


Using Eq.1, we calculate the cumulative sum of each number group as follows.


Why do we calculate cumulative sum? The purpose in this is to be able to simply run a binary search to determine which number group the digit belongs to in time. For example, consider i=40.

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 6 
1 2 3 4              --> 10
1 2 3 4 5            --> 15
1 2 3 4 5 6          --> 21
1 2 3 4 5 6 7        --> 28
1 2 3 4 5 6 7 8      --> 36 
1 2 3 4 5 6 7 8 9    --> 45
1 2 3 4 5 6 7 8 9 10 --> 56

Using binary search, we can find out that contains the digit. Then, using a linear search, we can simply derive the first four digits of to eventually find out the corresponding digit, 4.


Similarly, for i=55, we can figure out that the digit is indeed 1.


Next, we outline a F# implementation of the stated algorithm. We start with computing the cumulative sums of the lengths as follows. Continue reading “UVa 10706. Number Sequence with F#”

UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:


Using F#, we can derive 1500th Ugly Number in F#’s REPL as follows.

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

After computing the 1500th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

Please leave a comment in case of any question or improvement of this implementation. Thanks.

UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

See Also

see Collatz Problem a.k.a. 3n+1 ProblemCollatz Problem a.k.a. 3n+1 Problem.
see UVa100. 3n+1 ProblemUVa 100. 3n+1 Problem.

UVa 713. Adding Reversed Numbers

UVa 713: Adding Reversed Numbers is a straight-forward problem that can be solved using an ad-hoc algorithm. We have discussed a similar problem in a previous blog-post. However, this problem imposes following additional constraint—numbers will be at most 200 characters long–which necessitates the use of BigInteger. Following Java code shows such an ad-hoc algorithm that solves this problem by considering the stated constraints.

Please leave a comment if you have any question. Thanks.

See Also

see Party Schedule postSPOJ 42. Adding Reversed Numbers (ADDREV) with F#.

UVa 102. Ecological Bin Packing | with Brute-force search

The UVa 102: Ecological Bin Packing can be solved using brute-force search, as outlined in the following Java code snippet. Note that, the primary function getOPTConfiguration iterates over all possible bin arrangements, and determines the arrangement that requires minimum bottle moves for a given problem instance.

Please leave a comment if you have any question/comment. Happy coding!