Software Engineering

# Number of Rectangles in a Grid in Java

## The challenge#

Given a grid of size m x n, calculate the total number of rectangles contained in this rectangle. All integer sizes and positions are counted.

Examples:

``````numberOfRectangles(3, 2) == 18
numberOfRectangles(4, 4) == 100
``````

Here is how the 3×2 grid works (Thanks to GiacomoSorbi for the idea):

1 rectangle of size 3×2:

``````[][][]
[][][]
``````

2 rectangles of size 3×1:

``````[][][]
``````

4 rectangles of size 2×1:

``````[][]
``````

2 rectangles of size 2×2

``````[][]
[][]
``````

3 rectangles of size 1×2:

``````[]
[]
``````

6 rectangles of size 1×1:

``````[ ]
``````

As you can see (1 + 2 + 4 + 2 + 3 + 6) = 18, and is the solution for the 3×2 grid.

## The solution in Java code#

Option 1:

``````public class Solution {

public static int numberOfRectangles(int m, int n) {
return n*m*(n+1)*(m+1)/4;
}

}
``````

Option 2:

``````import java.util.stream.IntStream;

public class Solution {

public static int numberOfRectangles(int m, int n) {
return sumFromZeroTo(m) * sumFromZeroTo(n);
}

private static int sumFromZeroTo(int n) {
return IntStream.range(0, n + 1).sum();
}

}
``````

Option 3:

``````public class Solution {

public static int numberOfRectangles(int m, int n) {
return (m * m + m) * (n * n + n) / 4;
}

}
``````

## Test cases to validate our solution#

``````import org.junit.Test;
import static org.junit.Assert.assertEquals;
import java.util.Random;

public class RectTest {

private Solution soln = new Solution();

public int correctSolution(int m, int n) {
return (m * (m + 1) * n * (n + 1)) / 4;
}

@Test
public void shouldWork() {
Random r = new Random();
for(int i = 0; i < 15; i++) {
int m = r.nextInt(100) + 1;
int n = r.nextInt(100) + 1;

int solution = correctSolution(m, n);

assertEquals((solution + ""), solution, soln.numberOfRectangles(m, n), 0);
}
}

}
``````