समस्या
For each board size k from 1 through n, count unordered pairs of distinct squares on a k by k board where two knights cannot attack each other. A knight moves two squares in one axis and one in the other.
. x . x .
x . . . x
. . K . .
x . . . x
. x . x .K marks a knight and x its possible destinations, when those squares lie on the board. Swapping the two knights does not create another placement.
Implement two_knights(n).
Input
n: The largest board size to consider.
Output
Return n counts in order, for board sizes 1 through n.
सीमाएँ
1 ≤ n ≤ 10,000. Counts fit signed 64-bit integers.
उदाहरण
इनपुट:
n = 3
अपेक्षित आउटपुट:
expected = [0, 6, 28]इनपुट:
long long n = 3;
अपेक्षित आउटपुट:
std::vector<long long> expected = {0, 6, 28};इनपुट:
long n = 3;
अपेक्षित आउटपुट:
long[] expected = new long[] {0, 6, 28};व्याख्या
A 1 × 1 board cannot hold two knights. A 2 × 2 board has six pairs and no attacks. A 3 × 3 board has 36 pairs, of which eight attack, leaving 28.
इनपुट:
n = 1
अपेक्षित आउटपुट:
expected = [0]इनपुट:
long long n = 1;
अपेक्षित आउटपुट:
std::vector<long long> expected = {0};इनपुट:
long n = 1;
अपेक्षित आउटपुट:
long[] expected = new long[] {0};व्याख्या
Two distinct squares are required, but the board has only one.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Start with all unordered pairs of squares on each board, then subtract the pairs where knights attack.
संकेत 2
Only a small, fixed number of knight attack placements fit inside any 2 by 3 or 3 by 2 rectangle.
संकेत 3
Edge boards like 1 by 1 and 2 by 2 need to naturally produce zero attacking pairs.
अपेक्षित जटिलता
O(n) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।