MergeSqort | Topcoder Archive

Problem Statement

Consider a damaged version of Mergesort in which we don't divide the given array into halves. Instead, we will always split the array in such a way that the length of one part will be the square root of its current length.

More precisely, the algorithm in pseudocode looks as follows:

SqrtMergesort(an array A with n elements):
    if n == 1:
        do nothing and return A

    otherwise:
        write n asterisks to the standard output

        let n_left = floor( sqrt(n) )
        let n_right = n - n_left

        create two new arrays:
            B formed by the first n_left elements of A
            C formed by the last n_right elements of A

        let sortedB = SqrtMergesort(B)
        let sortedC = SqrtMergesort(C)

        return Merge(sortedB,sortedC)

In the above pseudocode, Merge is the standard function that merges two sorted arrays into one. Its implementation does not matter in this problem.

You are given n: the length of the array A. Compute and return the total number of asterisks printed to the standard output during the call of SqrtMergesort(A).

Definition

Class:: MergeSqort
Method:: count
Parameters:: int
Returns:: long
Method signature:: long count(int n)
(be sure your method is public)

Notes

Note that the number of asterisks printed is proportional to the running time of the computation.
floor(x) is the largest integer not exceeding x. For example, floor(4) = 4 and floor(5.9) = 5.
You may assume that the answer fits into a long.

Constraints

n will be between 1 and 10^9, inclusive.

Examples

```
2
```
```
Returns: 2
```
We print two asterisks, split the array into two 1-element parts, recursively sort each of them (which prints no asterisks) and merge the results together.
```
3
```
```
Returns: 5
```
We print three asterisks and then we make two recursive calls: one to sort a 1-element array (no asterisks printed) and the other to sort a 2-element array (2 asterisks).
```
24
```
```
Returns: 131
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.