Binary (0–1) triangle

Easy TimeO(n²) SpaceO(n²)

Given a row count n, return a triangle of alternating 1s and 0s as an array of n strings, row i holding i characters. The characters alternate along a row, and a row begins with 1 when its number is odd and 0 when it is even.

Examples

Example 1

Input
n = 5
Output
1
01
101
0101
10101
["1","01","101","0101","10101"]
Rows 1, 3 and 5 open on 1; rows 2 and 4 open on 0.

Example 2

Input
n = 2
Output
1
01
["1","01"]
Two rows, the odd one opening on 1 and the even one on 0.

The Code

function binaryTriangle(n) {
  const rows = [];
  for (let row = 1; row <= n; row++) {
    let line = "";
    for (let col = 1; col <= row; col++) {
      line += (row + col) % 2 === 0 ? "1" : "0";
    }
    rows.push(line);
  }
  return rows;
}
binaryTriangle(5);
Done

The first 19 calls, of 27. This one does not fit on a page.

Step through binaryTriangle(5) call by call

Explanation

Moving one column flips the character, and so does moving one row. A position’s digit therefore depends on the two counts together, never on what the position before it was.

  1. 1

    row is 1 and col is 1, so row + col is 2. (row + col) % 2 === 0 holds, and the "1" side of the conditional is appended. The inner loop stops there, because col is already row.

    1
    0

    row=1row + col=2

    rows.push("1")

  2. 2

    row is 2. At col 1 the sum is 3, which is odd, so the row opens on "0"; at col 2 it is 4 and the character is "1". Stepping one column changes the sum by one, which is what makes a row alternate.

    1
    0
    01
    1

    row=2row + col=3 then 4

    rows.push("01")

  3. 3

    row is 3. Stepping one row also changes the sum by one, so col 1 now gives 4 and the row opens on "1" — the opposite of the row above it.

    1
    0
    01
    1
    101
    2

    row=3row + col=4 … 6

    rows.push("101")

  4. 4

    row is 4, so the sums run 5 to 8 and the row opens on "0" again. No digit is ever read back: each position is decided entirely by where it sits.

    1
    0
    01
    1
    101
    2
    0101
    3

    row=4row + col=5 … 8

    rows.push("0101")

  5. 5

    row is 5 and the sums run 6 to 10, giving "10101". row++ then fails row <= n and the five strings are returned.

    1
    0
    01
    1
    101
    2
    0101
    3
    10101
    4

    row=5row + col=6 … 10

    return rows → 5 rows

More like this

All star & number patterns examples (12) →