इस समस्या में, हमें आकार N के तीन सरणी s1[], s2[] और s3[] दिए जाते हैं, जो N त्रिभुजों को दर्शाते हैं। हमारा कार्य दिए गए N त्रिभुजों में अद्वितीय त्रिभुजों की संख्या ढूंढना है।
एक त्रिभुज के अद्वितीय होने के लिए, उसकी सभी भुजाएं अद्वितीय होनी चाहिए यानी कोई अन्य त्रिभुज ऐसी भुजाएं नहीं रखना चाहिए।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
s1[] = {1, 5, 3} s2[] = {2, 3, 2} s3[] = {4, 2, 5}आउटपुट
1
व्याख्या
भुजाओं 1 2 4 वाला त्रिभुज अद्वितीय है।
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान उन त्रिभुजों की संख्या गिनना है जो अद्वितीय हैं।
इसके लिए, हम पहले प्रत्येक त्रिभुज की भुजाओं को सॉर्ट करेंगे और फिर एक मैप में स्टोर करेंगे, यदि इसके मान अद्वितीय हैं तो गिनती बढ़ाएं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h> using namespace std; int countUniqueTriangle(int a[], int b[], int c[], int n) { vector<int> triSides[n]; map<vector<int>, int> m; for (int i = 0; i < n; i++) { triSides[i].push_back(a[i]); triSides[i].push_back(b[i]); triSides[i].push_back(c[i]); sort(triSides[i].begin(), triSides[i].end()); m[triSides[i]] = m[triSides[i]] + 1; } map<vector<int>, int>::iterator itr; int uniqueTriCount = 0; for (itr = m.begin(); itr != m.end(); itr++) { if (itr->second == 1) if (itr->second == 1) uniqueTriCount++; } return uniqueTriCount; } int main() { int s1[] = { 1, 5 ,3 }; int s2[] = { 2, 3, 2 }; int s3[] = { 4, 2, 5 }; int N = sizeof(s1) / sizeof(s1); cout<<"The number of unique triangles is "<<countUniqueTriangle(s1, s2, s3, N); return 0; }आउटपुट
The number of unique triangles is 1
