समस्या
हर ऐसे धनात्मक पूर्णांकों के त्रिक a < b < c को खोजें जिनके लिए a² + b² = c² और a + b + c = perimeter हो। प्रत्येक त्रिक को [a, b, c] के रूप में लौटाएँ, जिसमें a और फिर b के बढ़ते क्रम में क्रमबद्ध किया गया हो। एक ही भुजाओं के क्रमचय (permutations) को शामिल न करें।
pythagorean_triplets(perimeter) को लागू करें।
इनपुट
perimeter: सभी तीनों भुजाओं का आवश्यक योग।
आउटपुट
निर्दिष्ट क्रम में त्रिकों की एक सूची लौटाएँ।
सीमाएँ
3 ≤ perimeter ≤ 100,000। यदि कोई त्रिभुज योग्य नहीं है तो एक खाली सूची लौटाएँ।
उदाहरण
इनपुट:
perimeter = 30
अपेक्षित आउटपुट:
expected = [
[5, 12, 13]
]इनपुट:
long long perimeter = 30;
अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {
{5, 12, 13}
};इनपुट:
long perimeter = 30;
अपेक्षित आउटपुट:
long[][] expected = new long[][] {
new long[] {5, 12, 13}
};व्याख्या
5 + 12 + 13 = 30 और 5² + 12² = 13²। यह एकमात्र योग्य त्रिक है।
इनपुट:
perimeter = 11
अपेक्षित आउटपुट:
expected = []इनपुट:
long long perimeter = 11;
अपेक्षित आउटपुट:
std::vector<std::vector<long long>> expected = {};इनपुट:
long perimeter = 11;
अपेक्षित आउटपुट:
long[][] expected = new long[][] {};व्याख्या
कोई भी बढ़ते क्रम के धनात्मक पूर्णांक दाएँ कोण वाले त्रिभुज का योग 11 नहीं होता।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Valid triple के लिए Pythagorean equation और perimeter sum, दोनों satisfy होने चाहिए।
संकेत 2
Sides के हर ordering को try करने के बजाय, perimeter से search limit करो।
संकेत 3
बस a < b < c रखें, और symmetric side choices से आने वाले duplicates skip करो।
अपेक्षित जटिलता
समय O(n^2), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।