We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
All upright combinations = ((M * N) * (M + 1) * (N + 1))/4 Total Diagonal Squares = (M * (N - 1)) + (N * (M - 1)) Diagonal M = Int(Total Diagonal Squares / Upright(N)) Diagonal N = Upright(N) Leftovers = Total Diagonal Squares - (Diagonal M * Diagonal N)
As long as Diagonal M and Diagonal N are greater than 1, use the following: All diagonal combinations = (((M * N) * (M + 1) * (N + 1))/4) + Leftovers Otherwise, All diagonal combinations = Diagonal M * Diagonal N
For Example: 3X2 Grid Upright Combinations = ((3 * 2) * (3 + 1) * (2 + 1))/4 = (6 * 4 * 3)/4 = 6 * 3 = 18 Total Diagonal Squares = (3 * (2 -1)) + (2 * (3 - 1)) = (3 * 1) + (2 * 2) = 3 + 4 = 7 Diagonal M = Int(7 / 2) = Int(3.5) = 3 Diagonal N = 2 Leftovers = 7 - (3 * 2) = 7 - 6 = 1 Since we know that a 3X2 grid has 18 combinations, for the diagonal we add the Leftovers, which is 1, to 18 and that gives us 19 for all diagonal combinations.
Now rinse and repeat for all smaller grids.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Project Euler #147: Rectangles in cross-hatched grids
You are viewing a single comment's thread. Return to all comments →
Let grid size is MxN (M<=N)
for upright rectangles of m <= M & n <= N
number of rectangles possible is (1+(M-m))*(1+(N-n)) usin this I can get upright rectangles of all sizes.
for diagonal rectangles I could only figure out for 1xn (and nx1) sizes.
how to figure out rest of the diagonal rectangles?
Any help!
All upright combinations = ((M * N) * (M + 1) * (N + 1))/4
Total Diagonal Squares = (M * (N - 1)) + (N * (M - 1))
Diagonal M = Int(Total Diagonal Squares / Upright(N))
Diagonal N = Upright(N)
Leftovers = Total Diagonal Squares - (Diagonal M * Diagonal N)
As long as Diagonal M and Diagonal N are greater than 1, use the following:
All diagonal combinations = (((M * N) * (M + 1) * (N + 1))/4) + Leftovers
Otherwise, All diagonal combinations = Diagonal M * Diagonal N
For Example: 3X2 Grid
Upright Combinations = ((3 * 2) * (3 + 1) * (2 + 1))/4 = (6 * 4 * 3)/4 = 6 * 3 = 18
Total Diagonal Squares = (3 * (2 -1)) + (2 * (3 - 1)) = (3 * 1) + (2 * 2) = 3 + 4 = 7
Diagonal M = Int(7 / 2) = Int(3.5) = 3
Diagonal N = 2
Leftovers = 7 - (3 * 2) = 7 - 6 = 1
Since we know that a 3X2 grid has 18 combinations, for the diagonal we add the Leftovers, which is 1, to 18 and that gives us 19 for all diagonal combinations.
Now rinse and repeat for all smaller grids.