Count Total Number of Colored Cells

Leetcode Problem:

• Count Total Number of Colored Cells

Summary

• Calculating the number of colored cells in a grid after n minutes

Approach

• The approach used is to calculate the number of colored cells in each minute and sum them up
• The number of colored cells in each minute is calculated as 2 times the number of odd-numbered cells that have not been colored yet
• The odd-numbered cells are calculated using the formula i * 2 + 1, where i is the current minute
• The initial number of odd-numbered cells is (i - 1) * 2 + 1, where i is 1
• The sum of colored cells in each minute is added to the total sum.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because the solution iterates over each minute from 1 to n
• The space complexity is O(1) because the solution only uses a constant amount of space to store the variables i, odd, and sum.

Solution Code:

class Solution {
public:
    long long coloredCells(int n) {
        int i = 1;
        int odd = (i - 1) * 2 + 1;
        long long sum = 0;
        for( ; i < n; i++){
            sum += odd*2;
            odd = i * 2 + 1;
        }
        return sum + odd;
    }
};