# Codingame Solution: 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