Build a Long String: Concatenation vs StringBuilder

medium JVM, Memory and Performance

Read n. Build one string that contains the numbers 1, 2, 3, ..., n written one after another with no separator (for n = 12 it is 123456789101112). Print the LENGTH of the string. For a big n the way you build the string decides if the program is fast or slow.

Constraints

1 <= n <= 5 * 10^4

Examples

Input

Output

String concatenation cost
StringBuilder
Amortized O(1) append

Solutions

Best approachTime O(n * digits)Space O(n * digits)

With s = s + i in a loop, each step copies the whole old string, so n steps cost O(n^2) copying. A StringBuilder (or a list and join) appends in amortized O(1), so the total is O(n).

Same code works in Java810172125Basic features only, so nothing changes between versions.

/*
 * Problem : Length of the built string.
 * Input   : One integer n.
 * Output  : The length.
 * Approach: Use a buffer.
 * Time    : O(n * digits)
 * Space   : O(n * digits)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: StringBuilder is a mutable buffer. append adds text at the end without copying the old text every time.
        StringBuilder builder = new StringBuilder();

        // Step 2: Append the numbers 1..n.
        for (long i = 1; i <= n; i++) {
            builder.append(i);
        }

        // Step 3: The length of the final text is the answer.
        return builder.length();
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}

Hints (1)

Why is s = s + i slow in a loop?