Problem Statement
Given the width and height of a rectangular grid, return the total number of rectangles (NOT counting squares) that can be found on this grid.
For example, width = 3, height = 3 (see diagram below):
__ __ __ |__|__|__| |__|__|__| |__|__|__|
In this grid, there are 4 2x3 rectangles, 6 1x3 rectangles and 12 1x2 rectangles. Thus there is a total of 4 + 6 + 12 = 22 rectangles. Note we don't count 1x1, 2x2 and 3x3 rectangles because they are squares.
Definition
- Class:
- RectangularGrid
- Method:
- countRectangles
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long countRectangles(int width, int height)
- (be sure your method is public)
Notes
- rectangles with equals sides (squares) should not be counted.
Constraints
- width and height will be between 1 and 1000 inclusive.
Examples
3
3
Returns: 22
See above
5
2
Returns: 31
__ __ __ __ __ |__|__|__|__|__| |__|__|__|__|__| In this grid, there is one 2x5 rectangle, 2 2x4 rectangles, 2 1x5 rectangles, 3 2x3 rectangles, 4 1x4 rectangles, 6 1x3 rectangles and 13 1x2 rectangles. Thus there is a total of 1 + 2 + 2 + 3 + 4 + 6 + 13 = 31 rectangles.
10
10
Returns: 2640
1
1
Returns: 0
592
964
Returns: 81508708664
1
1000
Returns: 499500
1000
1000
Returns: 250166416500
645
263
Returns: 7213197904
372
407
Returns: 5740659484
305
552
Returns: 7101355260
440
694
Returns: 23344693680
999
999
Returns: 249167416500
614
644
Returns: 39129899185
846
371
Returns: 24673670350
606
26
Returns: 64346490
737
913
Returns: 113288367720
166
731
Returns: 3699085070
215
799
Returns: 7404215580
2
211
Returns: 66466
723
584
Returns: 44617728480
458
320
Returns: 5380439360
900
647
Returns: 84850147296
744
131
Returns: 2390094476
502
322
Returns: 6544993574
537
786
Returns: 44590281701
268
220
Returns: 871537810
633
578
Returns: 33503068597
161
771
Returns: 3871720755
17
289
Returns: 6368064
181
278
Returns: 635171173
752
132
Returns: 2479079834
785
922
Returns: 131065984045
856
837
Returns: 128433985056
234
253
Returns: 878621055
398
406
Returns: 6538460614
684
295
Returns: 10202643440
616
85
Returns: 692432440
878
115
Returns: 2568223470
866
258
Returns: 12516785204
511
440
Returns: 12656388360
271
122
Returns: 274799876
1
2
Returns: 1
2
1
Returns: 1
2
2
Returns: 4
999
998
Returns: 248668915500
592
964
Returns: 81508708664
1000
1000
Returns: 250166416500
453
864
Returns: 38352535300
1
10
Returns: 45
964
999
Returns: 232017076860
999
998
Returns: 248668915500
592
964
Returns: 81508708664
1000
1000
Returns: 250166416500
453
864
Returns: 38352535300
1
10
Returns: 45
964
999
Returns: 232017076860
999
998
Returns: 248668915500
592
964
Returns: 81508708664
1000
1000
Returns: 250166416500
453
864
Returns: 38352535300
1
10
Returns: 45
964
999
Returns: 232017076860
999
998
Returns: 248668915500
592
964
Returns: 81508708664
1000
1000
Returns: 250166416500
453
864
Returns: 38352535300
1
10
Returns: 45
964
999
Returns: 232017076860