Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Highest truncated pyramid

Original Problem

Goal

You will be given a integer N, your goal is to draw the highest truncated pyramid that contains N “bricks”.
Each floor of a pyramid contains one brick more than the previous one.
Each brick is a * and each floor begins at the left of the line.
Be careful not to add spaces at the end of a line.

Input
Line 1: An integer N, the number of bricks you have
Output
The truncated pyramid
Constraints
1 ≤ N ≤ 1000

Solution

We got a number \(n\) of bricks to build a pyramid. The top rows are getting cut off to manage a number that wouldn't form a full pyramid. So how can we get the parameters of such a building? We basically need to start at row \(s\) and continue until row \(t\). That means, that our \(n\) is built by

\[n = \sum\limits_{i=s}^t i = \sum\limits_{i=1}^t i - \sum\limits_{i=1}^{s-1} i\]

Which can be simplified, using the triangular number sequence:

\[n = \frac{1}{2}t(t+1)-\frac{1}{2}(s-1)s = \frac{1}{2} (t^2 - s^2 + t + s)\]

So, how can we parametrize this diophantine equation? The easiest approach would be to brute-force a solution:

function search(n) {

  for (var s = 1; s <= n; s++) {

    for (var t = 1; t <= n; t++) {

      if (2 * n === (t * t - s * s + t + s)) {
        return [s, t];
      }
    }
  }
  return null;
}

With this algorithm, we can already pass all test cases like this:

[s, t] = search(n);

for (; s <= t; s++) {
    print("*".repeat(s));
}

But a lot of CPU cycles are wasted. Let's try to reduce the search space a bit. Since it doesn't make sense to increase \(t\) any further than \(2n\), we can use the inner condition as breakup condition:

\[t^2-s^2+t+s \leq 2n\Leftrightarrow t^2+t\leq 2n+s^2-s\Leftrightarrow t \leq \frac{1}{2}\left(\sqrt{8 n + 4 s (s - 1) + 1}-1\right)\]

Another optimization that can be made is based on the fact that powers of two can't be formed as a triangle. That means a power of two always needs to be represented as one row of length \(n\). Checking if \(n\) is a power of two can be done by a binary and against \(n-1\). If the result is zero, the number must have been a power of two. The search space can be brought down further. As the longest row appears with \(n\) being a power of two, all other pyramids must have at least two rows. That means we can half the search space of \(s\). After these optimizations, the search function can be implemented like this:

function search(n) {

  if ((n & (n - 1)) === 0)
    return [n, n];

  var x = n / 2;

  for (var s = 1; s <= x; s++) {

    var y = 2 * n + s * s - s;

    for (var t = 1; t * (t + 1) <= y; t++) {

      if (2 * n === (t*t - s*s + t + s)) {
        return [s, t];
      }
    }
  }
  return null;
}

If you're curious, the upper bound is still \(O(\frac{1}{2}n^2) = O(n^2)\). So back to the drawing board. Let's think a bit different. We know that the pyramid consists of \(n\) blocks. With these blocks we want to form \(k\) layers. So, back up from layer \(t\) this means:

\[n = t + (t-1) + (t-2) + ... + (t-k) = kt - \frac{k(k-1)}{2}\]

The first layer is simply \(s=1+t-k\). So what we do now is start with \(k\) at a large value and successively search for an integer \(t\) by solving the equation for \(t\):

\[t = \frac{n + \frac{k(k-1)}{2}}{k} = \frac{2n+k(k-1)}{2k}\]

With that equation, we can check for an integer solution and calculate \(t\). All we need is a proper starting value for \(k\), which we choose to be \(\lceil\sqrt{n}\rceil\). Finally, we can implement the parameter search in \(O(\sqrt{n})\):

function search(n) {

  if ((n & (n - 1)) === 0)
    return [n, n];

  var k = Math.ceil(Math.sqrt(n));

  while (k > 0) {
    var p = 2 * n + k * (k - 1);
    var q = 2 * k;
    if (p % q === 0)
        return [1 + p / q - k, p / q];
    k--;
  }
  return null;
}

« Back to problem overview