CareerCup

1. squares in NxN grid

1X1	 ->  (N)^2
2X2	 ->  (N-1)^2
3X3  ->  (N-2)^2
...
NxN  ->  (1)^2
So, total no. of squares=sigma(N^2) over N
					=(N)*(N+1)*(2*N+1)/6

2.squares in MxN grid

let M>N //swap if M<N
let k=M-N
1x1  ->  (N+k)x(N)
2x2  ->  (N-1+k)x(N-1)
3X3  -> (N-2+k)x(N-2) 
...
NxN  ->(1+k)x(1)
So, total no. of squares=sigma((N+k)*(N)) over N
					=sigma(N^2 + k*N)
					=sigma(N^2) +k*sigma(N)
					=(N)(N+1)(2*N+1)/6 + k*N*(N+1)/2

3.rectangles in MxN grid

In an MxN grid you have M+1 horizontal lines
and N+1 vertical lines to enclose a rectangle.
If we choose 2 out of M+1 lines and 2 out of N+1 lines then the intersection of these 4 lines makes a rectangle.

so,answer is 	  (N+1)C(2) * ((M+1)C(2))   		//nCr
			=(N*(N+1)/(2)) * (M*(M+1)/2)

// assume that the numbers of rectangles before index(i,j) is s
// when the rect in index(i,j) is included, another (i+1)*(j+1) rectangles add to s

int sum = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
sum += (i+1)*(j+1);
}
}
return sum;

Is the grid fill with 1s and 0s?

Number of Squares:

for (int i= N through 0){
	numSquare += i^2;
}
return numSquare;

Assumption M<=N

For no of squares in MxN

Size of square:			1	2	3	4.....	k...		M-1		M
No of squares in row:	N	N-1	N-2	N-3	N-k+1	N-M+2	N-M+1
No of squares in col:	M	M-1	M-1	M-1	M-k+1	2		1
Total no of squares = no of squares in row * no of squares in col
sigma [(N-k+1)*(M-k+1)] for k from 1 to M

For rectangles

Length of rectange		1	2	...	k	...	N-1	N
No of rectange			N	N-1		N-k+1	2	1
Total rectangles  = N*(N+1)/2
Height of rectange		1	2	...	k	...	M-1	M
No of rectange			M	M-1		M-k+1	2	1
Total rectangles  = M*(M+1)/2
Total no of rectanges = M*N*(M+1)*(N+1)/4

This solution uses DP, however, it's not as good as those that provide a cool formula, plus its demonstration, for calculating the value :(

Number of squares:
The idea is that for getting the number of possible squares at cell (i, j), we want to add the existing ones at (i-1,j) + (i, j-1) while ignoring duplications, i.e., (i-1,j-1). Then, we want to add all new squares that have cell (i, j) as part of them, which in this case is the value of min(i, j) for the squares of size 1, 2, 3 ... min (i, j) that have cell (i, j) at its bottom-right corner.

Hence,
F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + min(i, j)

You can fill the matrix top-down while reading left to right.

Number of rectangles:

Same idea as previous one, except that the number of new rectangles added at cell (i, j) that include such cell is given by i * j.

F(i, j) = F(i - 1, j) + F(i, j - 1) - F(i - 1, j - 1) + i * j

Time complexity: O(n^2), sadly...
Space complexity: O(n^2), ouch...

Solve reccurance equation:
C(1)=n; C(n)=C(n-1)*2 - n + N + 1
The solution:
C(n) = 2^(n-1) (n+N-2)+n-N+1

Notice, with adding row we only doubling previous squares (each has shifted copy) plus aad all covering new width