कठिन 1 हल किया गया 100.0% स्वीकृति

Cut a Rectangle Into Squares

Find the fewest straight cuts needed to produce only squares.

आप क्या सीखेंगे

  • Define a DP table over width and height
  • Try every horizontal and vertical cut
  • Reuse results for smaller rectangles

समस्या

अनुवाद दिखाएँ

On each move, choose one rectangle and cut all the way across it, parallel to a side, making two rectangles with positive integer side lengths. Continue until every piece is a square. Squares may have different sizes. Count cuts, not pieces.

Implement rectangle_cutting(height, width).

Input

height: The starting rectangle height.

width: The starting rectangle width.

Output

Return the minimum number of cuts.

सीमाएँ

1 ≤ height, width ≤ 500. Rotation does not change the answer.

उदाहरण

उदाहरण 1
इनपुट:
height = 2
width = 3

अपेक्षित आउटपुट:
expected = 2
इनपुट:
long long height = 2;
long long width = 3;

अपेक्षित आउटपुट:
long long expected = 2;
इनपुट:
long height = 2;
long width = 3;

अपेक्षित आउटपुट:
long expected = 2;

व्याख्या

Cut off a 2 × 2 square, leaving a 2 × 1 rectangle. One more cut splits the remainder into two unit squares.

उदाहरण 2
इनपुट:
height = 4
width = 4

अपेक्षित आउटपुट:
expected = 0
इनपुट:
long long height = 4;
long long width = 4;

अपेक्षित आउटपुट:
long long expected = 0;
इनपुट:
long height = 4;
long width = 4;

अपेक्षित आउटपुट:
long expected = 0;

व्याख्या

The starting rectangle is already a square.

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

A rectangle can be solved by splitting it into two smaller rectangles and combining their best answers.

संकेत 2

Try every possible horizontal and vertical cut to find the minimum.

संकेत 3

Memoization or a table is helpful because many subrectangles repeat.

अपेक्षित जटिलता

O(h*w*(h+w)) time, O(h*w) extra space

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

# कोडर भाषा समय मेमोरी AI रिव्यू समाधान
1 ННикита Python 954 ms - 4/5 कोड देखें

दूसरों से सीखें

समुदाय समाधान

स्पॉइलर अलर्ट: नीचे 1 पूरा समाधान पहले खुद हल करने की कोशिश करें। आप फिर भी अन्य डेवलपर्स का कोड और AI समीक्षा देख सकते हैं। चर्चा में शामिल होने के लिए साइन इन करें और चुनौती हल करें।