A number triangle is built like Pascal's triangle, but each entry sums three neighbors from the row above instead of two.
Row 1 is a single 1. To get row r (for r > 1) from row r - 1: row r has two more entries than row r - 1, sticking out by one extra position on each side. Line up row r's middle entry with row r - 1's middle entry; then every entry of row r equals the sum of the entry diagonally above-left, the entry directly above, and the entry diagonally above-right in row r - 1 — treating any of those three positions that fall outside row r - 1 as 0.
So row 1 is [1], row 2 is [1, 1, 1], row 3 is [1, 2, 3, 2, 1], row 4 is [1, 3, 6, 7, 6, 3, 1], and so on — row r always has 2r - 1 entries.
Given a row number n (1-indexed), return the 1-indexed position from the left of the first even value in row n. If row n has no even value at all, return -1.
Example
Row 3 is [1, 2, 3, 2, 1]; the first even value, 2, sits at 1-indexed position 2.
Constraints
- 1 <= n <= 10^9
- Row values grow combinatorially, so building the actual row is only feasible for small n.
Intuition
A first pass builds the actual row: start from row 1 ([1]) and, row by row, sum each entry's up-to-three parents from the row above, until row n is built — then scan that row left to right for the first even value.
function triangleNumbers(n) {
// Row 1 is just [1]; row[i] holds the entry at position i (0-indexed) of the current row.
let row = [1];
// Build each row from the one before it, up to row n.
for (let r = 2; r <= n; r++) {
// Row r has two more entries than row r - 1: one extra sticking out on each side.
const next = new Array(row.length + 2).fill(0);
// Every entry of the previous row fans out into the three positions below it
// (above-left, above, above-right) in the new row.
for (let i = 0; i < row.length; i++) {
next[i] += row[i]; // above-left parent
next[i + 1] += row[i]; // above parent
next[i + 2] += row[i]; // above-right parent
}
row = next;
}
// Scan the finished row left to right for the first even value.
for (let i = 0; i < row.length; i++) {
if (row[i] % 2 === 0) return i + 1; // 1-indexed position
}
// No even value anywhere in the row.
return -1;
}This is O(n²) time to build every row up to n — each of the n rows is itself up to 2n - 1 entries long, and only the current and next row are ever live at once, so the space is O(n), not O(n²). Worse, the entries themselves grow combinatorially, overflowing ordinary number types long before n gets anywhere near the stated 10^9 bound. Can we do better?
Key observation: we never actually need the row's values — only which entries are even. Since every entry is the sum of up to three parents, whether an entry is even or odd depends only on the parities of its parents, not their magnitudes. Reducing the whole triangle mod 2 turns it into a much smaller, self-similar pattern driven by n's binary representation — the same kind of parity reasoning behind Bit manipulation.
Tracking that reduced pattern shows a fixed rule that holds for every row from 3 onward: an odd row number always puts the first even entry at position 2; a row number divisible by 4 always puts it at position 3; and a row number that's even but not divisible by 4 always puts it at position 4. Rows 1 and 2 are the only two rows that are entirely odd, so they're handled as a direct special case instead.
Bridging the two: the walkthrough below still scans an actual row left to right, because that's the clearest way to see what "first even position" means — but the stored optimal solution never builds a row at all. It reads off n's parity and n % 4 and returns the position directly, in O(1). Row 6 below is even with 6 % 4 == 2, and the scan lands on position 4 — exactly what the closed-form formula returns for n = 6, without ever materializing a single row entry.
Walking it through:
row 6 = [1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1] — scanning for the first even value
Start scanning from the left; row 6 opens with three odd entries in a row.
Still odd — nothing to report yet.
A third odd entry; the scan keeps moving right.
The first even value, 30, sits at 1-indexed position 4 — matching the closed form's "n even, n % 4 == 2 → 4" rule for n = 6.
row 2 = [1, 1, 1] — the only nontrivial row with no even value at all
Row 2 is entirely odd. Start the same left-to-right scan.
Still odd.
The last entry is also odd.
The scan finishes without ever finding an even value. Rows 1 and 2 are the only two rows this happens for — the closed-form solution special-cases n = 1 and n = 2 directly instead of scanning.
Optimization
Closed-form parity formula
Building row n directly is O(n²) and its values overflow long before n gets large, so the trick is to reason about parity only, without ever computing the actual values.
Rows 1 and 2 are all-odd, so they have no even entry. From row 3 on, tracking the pattern of "position of the first even entry" against n's residue mod 4 shows a fixed, repeating rule:
- n odd → the first even value is always at position 2.
- n even and divisible by 4 → the first even value is always at position 3.
- n even and n % 4 == 2 → the first even value is always at position 4.
This pattern is a known property of the parity structure of this "trinomial" triangle (each entry mod 2 follows a self-similar, Pascal's-triangle-like fractal driven by n's binary representation), and it holds for every n >= 3.
O(1) time and space — a couple of modulo checks regardless of how large n is.
function triangleNumbers(n) {
// Rows 1 and 2 are entirely odd: [1] and [1, 1, 1].
if (n === 1 || n === 2) return -1;
// From row 3 on, the position of the first even value depends only on n mod 4.
if (n % 2 === 1) return 2;
if (n % 4 === 0) return 3;
return 4; // n even, n % 4 === 2
}Brute force: build the row
Simulate the triangle row by row using a centered array (index 0 is the middle of the row), where each entry sums whichever of the up-to-three parents from the previous row exist. Once row n is built, scan left to right for the first even value.
O(n²) time to build every row up to n (only the current and next row are ever live, so space is O(n), not O(n²)), and the entries themselves grow combinatorially — this only works for small n and would never finish (or fit in memory) anywhere near the 10^9 bound, which is exactly why the closed-form formula above is the one actually used.
function triangleNumbers(n) {
// row[i] holds the value at centered offset (i - (row.length - 1) / 2).
let row = [1];
for (let r = 2; r <= n; r++) {
const next = new Array(2 * r - 1).fill(0);
// Row r is one entry longer on each side than row r - 1, so parent index i
// (in row r - 1) lines up with child indices i, i + 1, i + 2 in "next".
for (let i = 0; i < row.length; i++) {
next[i] += row[i];
next[i + 1] += row[i];
next[i + 2] += row[i];
}
row = next;
}
for (let i = 0; i < row.length; i++) {
if (row[i] % 2 === 0) return i + 1;
}
return -1;
}Complexity analysis
Time complexity: O(1). Here's why:
- The base-case check (
n === 1 || n === 2) and the two parity checks that follow it (n % 2,n % 4) are each a single comparison. - No loop ever touches
n— the same handful of operations run whethernis 3 or 10^9.
So the total time is a fixed number of operations regardless of input size — O(1) — a decisive improvement over the brute force's O(n²) row-building, which wouldn't finish anywhere near the stated bound.
Space complexity: O(1). Here's why:
- Only the input
nand a couple of comparison results are ever held — no row or auxiliary array is allocated. - Contrast with the brute force, which keeps a full row in memory (up to
2n - 1entries, each growing combinatorially large).
So the extra space is O(1), independent of how large n gets.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| n = 1 | -1 | Row 1 — a single odd entry, so there's no even value at all. |
| n = 2 | -1 | Row 2 — still entirely odd ([1, 1, 1]); the only other row with no even value. |
| n = 11 | 2 | Odd row number: the first even value always sits at position 2, for every row from 3 on. |
| n = 16 | 3 | Row number divisible by 4: the first even value always sits at position 3. |
| n = 18 | 4 | Even row number that isn't divisible by 4 (18 % 4 == 2): the first even value always sits at position 4. |
| n = 123456789 | 2 | A large odd row number — the closed form answers instantly regardless of scale, unlike the O(n²) row-building brute force. |
Try it yourself
Write your solution against the real judge before checking the reference.