Ad
  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution

  • Custom User Avatar

    Not efficient, but he use primitive types, not wrapper class. Is valid solution.

  • Default User Avatar
  • Default User Avatar

    if someone new is having doubt here go read about String pool, basically in each concatenation a new string object is created and it consumes way too much memory

  • Default User Avatar

    @olee2002 It's good that you benchmarked it! There are a couple possibilities.

    1. Microbenchmarks in Java are notoriously difficult.

    2. As you suggested, the O(n^2) version could very well be faster for small n.

    Note that strings in Javascript are also immutable, so you get the same situation. The solution is less clear, but I think string.join is an O(n) solution in JS. "Naive" concatenation with + in JS may use something like StringBuilder under the hood depending on the browser engine (but I wouldn't count on it), whereas in Java it's guaranteed to be O(n^2).

  • Custom User Avatar

    I am a newbie to Java but interestingly this solution runs faster than the StringBuilder. I tried to run them both to see which one runs faster. But I guess its because the string isn't long enough? I am from the Javascript land so I was excited to see this approach since this looks close to JS.

  • Default User Avatar

    Because a String object can't be changed. In this code in the line "s+=string;" a new string is created every iteration.

  • Default User Avatar

    Concatenation takes time relative to the lengths of the input strings. The left side of the concatenation carries all previous concatenations with it, so you get a total time on the order of (1 + 2 + 3 + ... + repeat) = (repeat * (repeat + 1) / 2) which is O(n^2), n = repeat.

    Concatenations on a StringBuilder are constant time amortized. So the result is 1 + 1 + ... + 1, repeat times. O(n).

  • Default User Avatar

    I know that (and why) StringBuilder is faster, but how does this solution run in O(n^2)?