Count Total Number of Colored Cells

Easy
711.

Count Total Number of Colored Cells

Count Total Number of Colored Cells is an easy coding problem on math and simulation, asked in Amazon, TCS and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var coloredCells = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Total Number of Colored Cells — Problem & Solution

Count Total Number of Colored Cells solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Total Number of Colored Cells is an easy coding problem on math and simulation, asked in Amazon, TCS and Infosys interviews.

  • 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

Hints for Count Total Number of Colored Cells

  1. Hint 1

    Draw the first three minutes: the shape is a diamond, not a square.

  2. Hint 2

    Minute k adds a ring of 4(k - 1) cells.

  3. Hint 3

    Summing those rings gives a closed form in n.

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

Java

public static int coloredCells(int n) {
    long v = n;
    return (int) (2 * v * v - 2 * v + 1);
}

C++

int coloredCells(int n) {
    long long v = n;
    return (int) (2 * v * v - 2 * v + 1);
}

JavaScript

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

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

All 337 math problems · the whole catalogue