☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 11

Easy TUF ID 403 A2Z

Java source ↗ Edit this article ↗

Problem

Given an integer n, print a binary number triangle with n rows. Row i (0-based) contains i + 1 digits that alternate between 1 and 0. The first row starts with 1, the second with 0, the third with 1, and so on: even-indexed rows start with 1, odd-indexed rows start with 0. Because the lengths and starting digits are arranged this way, every row ends with 1.

Output format: digits are printed adjacent with no separators (a space-separated variant is a one-token change), every row ends with a newline, and there are no trailing spaces. n = 0 prints nothing.

Constraints: 0 ≤ n ≤ 100 is typical.

Example 1

n = 5

1
01
101
0101
10101

Row i has i + 1 digits; the starting digit alternates by row, and the last digit of every row is 1.

Example 2

n = 2

1
01

The second row starts with 0 and alternates to 1.

State versus formula

This pattern is a small lesson in two ways of producing a sequence. The first is stateful: keep a variable holding the current digit, reset it at the start of each row, and flip it after every print. The second is closed-form: notice that the digit at (i, j) depends only on the parity of i + j, and compute it directly. Both are correct; the stateful version mirrors how you would describe the pattern aloud, while the formula is what you need when you want the value of an arbitrary cell without replaying the sequence. A third view, that each row is a suffix of the last row, shows how recognising structure can remove a loop entirely.

All approaches return the pattern as a String so the tests can compare it with expected literals.

Approach 1: Toggle a running bit

Intuition. At the start of row i, set bit to 1 if i is even and 0 if odd. Print bit, then flip it with bit = 1 - bit, and repeat i + 1 times. The flip is the whole mechanism: after printing 1 the next is 0, after 0 the next is 1.

Algorithm.

  1. For i from 0 to n - 1: bit = (i % 2 == 0) ? 1 : 0.
  2. For j from 0 to i: append bit; bit = 1 - bit.
  3. Append \n.
static String toggle(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        int bit = (i % 2 == 0) ? 1 : 0;              // even rows start with 1, odd rows with 0
        for (int j = 0; j <= i; j++) {
            sb.append(bit);
            bit = 1 - bit;                           // flip for the next column
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): n(n+1)/2 digits. Space O(n^2) for the output, O(1) extra.

Note that bit is an int and sb.append(bit) writes "0" or "1" via append(int). If bit were a char holding '0', the flip 1 - bit would be nonsense, so keep the state numeric.

Approach 2: Parity formula

Intuition. Check the first few cells. Row 0: (0,0) is 1. Row 1: (1,0) is 0, (1,1) is 1. Row 2: 1, 0, 1 at j = 0, 1, 2. In every case the digit is 1 when i + j is even and 0 when it is odd. Why: the row starts with 1 exactly when i is even, and each step right flips the digit, which is the same as adding 1 to i + j. So (i + j) % 2 == 0 is a complete description of the cell, and no state is carried between cells.

Algorithm.

  1. For i from 0 to n - 1, for j from 0 to i: append '1' if (i + j) % 2 == 0 else '0'.
  2. Append \n after each row.
static String parityFormula(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            sb.append((i + j) % 2 == 0 ? '1' : '0');
        }
        sb.append('\n');
    }
    return sb.toString();
}

Dry run for n = 4:

i i + j for j = 0..i digits
0 0 1
1 1, 2 01
2 2, 3, 4 101
3 3, 4, 5, 6 0101

Complexity. Time O(n^2), space O(1) extra.

Here the cell values are chars ('1' and '0') and append(char) is used. Both append(int) with 1 and append(char) with '1' produce the same text, but mixing them up, for example append((char) 1), produces an invisible control character.

Approach 3: Every row is a suffix of the last row

Intuition. Line the rows up on the right instead of the left:

    1
   01
  101
 0101
10101

Each row is the tail of the one below it. So the whole triangle is determined by the last row: row i is the last i + 1 characters of row n - 1. Build that final row once, a string of length n that ends in 1 and alternates leftwards (character k is 1 when n - 1 - k is even), and then slice it. StringBuilder.append(CharSequence, start, end) copies the slice without creating an intermediate String.

Algorithm.

  1. Build last of length n: character k is '1' if (n - 1 - k) % 2 == 0, else '0'.
  2. For i from 0 to n - 1: append last[n - 1 - i .. n) and \n.
static String suffixes(int n) {
    StringBuilder last = new StringBuilder();
    for (int k = 0; k < n; k++) last.append((n - 1 - k) % 2 == 0 ? '1' : '0');   // ends with 1, alternates leftwards
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < n; i++) out.append(last, n - 1 - i, n).append('\n');     // the last i+1 characters
    return out.toString();
}

Complexity. Time O(n^2) for copying the slices, space O(n) extra for last.

That this agrees with the parity formula is a two-line check: position j of row i is last[n - 1 - i + j], which is '1' when n - 1 - (n - 1 - i + j) = i - j is even, and i - j has the same parity as i + j.

Edge cases and pitfalls