Get started

Count Total Number of Colored Cells — Easy Problem & Solution

On an infinite grid you colour one cell in minute 1. In every later minute you colour every uncoloured cell that shares an edge with an already-coloured cell.

  • Difficulty: Easy
  • Topics: Math, Simulation
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

On an infinite grid you colour one cell in minute 1. In every later minute you colour every uncoloured cell that shares an edge with an already-coloured cell.

Return how many cells are coloured at the end of minute n.

Example 1

Input: n = 1
Output: 1
Explanation: One cell.

Example 2

Input: n = 2
Output: 5
Explanation: The centre plus its four edge neighbours.

Example 3

Input: n = 3
Output: 13
Explanation: The diamond grows by 8 cells.

Constraints

  • 1 <= n <= 20000

How to solve Count Total Number of Colored Cells

The coloured region is the diamond of cells within Manhattan distance n - 1 of the start. Its size follows from summing the ring sizes.

Approach

  1. Minute 1 colours 1 cell; minute k > 1 adds a ring of 4(k - 1) cells.
  2. Total = 1 + 4(1 + 2 + … + (n-1)) = 1 + 4 · n(n-1)/2 = 2n² - 2n + 1.
  3. Return that value.

Why it works

The set reachable in k minutes is exactly the cells at Manhattan distance at most k - 1, and the number at distance exactly d > 0 is 4d — one for each of the four diagonal edges of the diamond.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • (2n - 1)² counts a square, not a diamond, and overcounts badly.
  • At n = 20000 the answer is about 8 × 10^8, which fits in a 32-bit integer — but the intermediate 2n² must not be computed in a narrower type.

Reference solution

Python

def coloredCells(n: int) -> int:
    return 2 * n * n - 2 * n + 1

JavaScript

var coloredCells = function(n) {
    return 2 * n * n - 2 * n + 1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue