2579. Count Total Number of Colored Cells

problem

solution

recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
long long coloredCells(int n) {
// 1: 1
// 2: 1 + 4 = f(1) + 2*4-4
// 3: 5 + 8 = f(2) + 3*4-4
// 4: 13 + 12= f(3) + 4*4-4
// 5: 25 + 16
if(n==1) return 1;
else return coloredCells(n-1) + n*4-4;
}
};

i solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
long long coloredCells(int n) {
// 1: 1
// 2: 1 + 4 = f(1) + 2*4-4
// 3: 5 + 8 = f(2) + 3*4-4
// 4: 13 + 12= f(3) + 4*4-4
// 5: 25 + 16
if(n==1) return 1;
// else return coloredCells(n-1) + n*4-4;
long long ret = 1, tmp = 0;
for(int i=2 ;i<=n; ++i){
tmp = ret + i*4-4;
ret = tmp;
}
return ret;
}
};

analysis

  • time complexity : could lower to O(1) (long long)n * n + (long long)(n - 1) * (n - 1);
  • space complexity O(1)