Count Total Number of Colored Cells

medium math pattern

Problem

An infinitely large grid starts completely uncolored. At minute 1 you color one cell blue. During every following minute, every uncolored cell that shares an edge with a blue cell becomes blue as well. Given an integer n (1 ≤ n ≤ 10⁵), return how many cells are colored after n minutes.

Inputn = 4

Output25

Minute 1 colors the center cell; minutes 2, 3 and 4 add diamond rings of 4, 8 and 12 cells: 1 + 4 + 8 + 12 = 25.

n (minutes, 1–8)

def colored_cells(n):
    total = 1                    # minute 1: the single center cell
    for m in range(2, n + 1):
        total += 4 * (m - 1)     # minute m adds a ring of 4(m-1) cells
    return total                 # closed form: 2*n*n - 2*n + 1

function coloredCells(n) {
  let total = 1;                 // minute 1: the single center cell
  for (let m = 2; m <= n; m++) {
    total += 4 * (m - 1);        // minute m adds a ring of 4(m-1) cells
  }
  return total;                  // closed form: 2*n*n - 2*n + 1
}

long coloredCells(int n) {
    long total = 1;              // minute 1: the single center cell
    for (int m = 2; m <= n; m++) {
        total += 4L * (m - 1);   // minute m adds a ring of 4(m-1) cells
    }
    return total;                // closed form: 2L*n*n - 2L*n + 1
}

long long coloredCells(int n) {
    long long total = 1;         // minute 1: the single center cell
    for (int m = 2; m <= n; m++) {
        total += 4LL * (m - 1);  // minute m adds a ring of 4(m-1) cells
    }
    return total;                // closed form: 2LL*n*n - 2LL*n + 1
}

Explanation

The colored region is always a diamond: a cell gets colored exactly when its Manhattan distance from the center is at most m − 1 at minute m. So instead of simulating a huge grid, we only need to count how many new cells each minute contributes.

The cells added at minute m are exactly those at Manhattan distance m − 1 from the center — the boundary ring of the diamond. A diamond of radius r ≥ 1 has 4r boundary cells (one per lattice point of the rotated square), so minute m adds 4(m − 1) cells.

Summing the rings gives total = 1 + 4·(1 + 2 + … + (n − 1)) = 1 + 4·n(n − 1)/2 = 2n² − 2n + 1. The loop in the code accumulates the same sum term by term; you can also return the closed form directly in O(1).

Walking through the default example n = 4: minute 1 colors the center (total 1), minute 2 adds 4·1 = 4 (total 5), minute 3 adds 4·2 = 8 (total 13), and minute 4 adds 4·3 = 12 (total 25). The closed form agrees: 2·16 − 8 + 1 = 25.

The loop runs n − 1 times doing constant work, so time is O(n) (or O(1) with the formula) and space is O(1). Since n can be 10⁵, the answer approaches 2·10¹⁰, which overflows 32-bit integers — hence long/long long in Java and C++.

Time: O(n) Space: O(1)