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
Code language: Java (java)

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

1 rectangle of size 3×2:

[][][] [][][]
Code language: Java (java)

2 rectangles of size 3×1:

[][][]
Code language: Java (java)

4 rectangles of size 2×1:

[][]
Code language: Java (java)

2 rectangles of size 2×2

[][] [][]
Code language: Java (java)

3 rectangles of size 1×2:

[] []
Code language: Java (java)

6 rectangles of size 1×1:

[ ]
Code language: Java (java)

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; } }
Code language: Java (java)

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(); } }
Code language: Java (java)

Option 3:

public class Solution { public static int numberOfRectangles(int m, int n) { return (m * m + m) * (n * n + n) / 4; } }
Code language: Java (java)

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); } } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments