Sort 115 Discussions, By:
Please Login in order to post a comment
The reason beind mn - 1 can be understood like this. Forget about any grid for a moment, just imagine a simple piece of paper. Any cut on the paper will give rise to a new piece. If you make 1 cut to a single piece, it will give rise to 1 extra piece. If you further make a cut on any of those pieces, your count increases by one.
In total, we need mn pieces, given each is 1x1. We don't have to make mn cuts, because there is already one piece at the beginning. So, we make mn - 1 cuts.
The topic of cutting 3x2 piece of paper is clearly explained over this problem section. The clarity of the details is the main reason that I ma always find the page for a clear understanding of some topics printer driver is unavailable. The paper cut options explained clearly with the proper image help.
Make sure you have enough memory to store the numbers ;)
Cheers mate. I was absolutely sure i figured it out so WHY IT WAS FAILING.
kinda silly, because it's a math problem, not core Java or Data structures problem.
kinda stupid. you would only need to add 1 line if the data types were correct.
Not a problem in Python
Each time a piece of paper is cut it becomes 2 pieces, adding 1 to the total number of pieces. Therefore to make x pieces from 1 piece there needs to be x-1 cuts, so the final answer is (n*m)-1.
Interestingly, this principle means that the cuts can be made in any order and configuration.
Your last line is spectacularly helpful and fun.
its working 1×1 cut
but 2×2 cut
what is formula
For this problem to be ranked easy, it would be nice to see an example that wasn't one-dimensional solved all the way thru, to ensure we understand the rules for cutting. That is, sure, you can't fold or place them on top of eachother, but it is unclear whether you can hold multiple pieces of paper side by side as you cut. It seemed perfectly logical that one could, so I think an example where m, n both >1 would have cleared that question about the rules right up.
ye i was thinking the exact same thing myself
Actually, even Medium or Hard problems should just be harder or trickier to get working, not to understand what they are asking for. So what I said, but more so.
Admittedly, In Real Life, sometimes understanding what is actually needed, especially if it is non-identical to what was asked for, is a very important part of the problem. One big difference between here and LeetCode is that the problem descriptions tend to be more straightforward there, but more "fun" here. Glad they both exist.
The answer is always one less than the number of 1x1 squares. Proof by induction: a single square takes zero cuts. If you have a rectangle of n squares that takes n-1 cuts, if you add a row or column of m squares, you are increasing the number of cuts by m as well, so the property is invariant.
So how did you come up with this? I found the answer but not elegantly. Did it take you a long time or trial-and-error or did you have a method for reducing this problem to its essential parts that made the formula clear?
I found this a slightly different way, not as elegant as this logic, but still might be of interest to you.
I approached creating an equation by figuring out how many cuts I would need in each direction:
If I start in n orientation, I would cut (n-1) times. then for m orientation, I would cut (m-1) times for each of the n number of strips, so (m-1)*n.
Thus, the number of cuts needed would be
cuts= (n -1) +(m-1)*n.
cuts= n - 1 + m*n -n
I thought of the same idea