Given N triangles along with the length of their three sides as a, b and c. The task is to count the number of unique triangles out of these N given triangles. Two triangles are different from one another if they have at least one of the sides different.
Examples:
Input: arr[] = {{3, 1, 2}, {2, 1, 4}, {4, 5, 6}, {6, 5, 4}, {4, 5, 6}, {5, 4, 6}};
Output: 3Input: arr[] = {{4, 5, 6}, {6, 5, 4}, {1, 2, 2}, {8, 9, 12}};
Output: 3
This problem has been solved using ordered set of STL in the previous post. Approach: We will be discussing the operator overloading based approach to solve this problem where we are going to overload the relational operator (==) of our class.
- Since any two sets of sides of a triangle, say {4, 5, 6}, {6, 5, 4}, are said to be equal if each element in one set corresponds to the elements in the other. So we will be checking each element of one set with the elements of the other set and keep a count of it. If the count will be the same, both the sets can simply be considered as equal. Now we have simply compared the sets using the relational operator to find the unique number of sets.
- To get the number of unique sets, we can follow an approach of comparing the current set’s uniqueness with the sets ahead of it. So, if there will be k sets of the same type, only the last set would be considered to be unique.
Below is C++ implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure to represent a Triangle// with three sides as a, b, cstruct Triangle { int a, b, c;public: bool operator==(const Triangle& t) const;};// Function to overload relational// operator (==)bool Triangle::operator==(const Triangle& t) const{ int cnt = 0; if ((this->a == t.a) || (this->a == t.b) || (this->a == t.c)) { cnt++; } if ((this->b == t.a) || (this->b == t.b) || (this->b == t.c)) { cnt++; } if ((this->c == t.a) || (this->c == t.b) || (this->c == t.c)) { cnt++; } // If all the three elements a, b, c // are same, triangle is not unique if (cnt == 3) { return false; } // For unique triangle return true return true;}// Function returns the number// of unique Trianglesint countUniqueTriangles(struct Triangle arr[], int n){ // Unique sets int uni = 0; for (int i = 0; i < n - 1; i++) { // Check on uniqueness for a // particular set w.r.t others int cnt = 0; for (int j = i; j < n - 1; j++) { // Checks if two triangles // are different if (arr[i] == arr[j + 1]) cnt++; } // If count of unique triangles // is same as the number of remaining // triangles then, increment count if (cnt == n - 1 - i) uni++; } // Since last element that // remains will be unique only return uni + 1;}// Driver Codeint main(){ // An array of structure to // store sides of Triangles struct Triangle arr[] = { { 3, 2, 2 }, { 3, 4, 5 }, { 1, 2, 2 }, { 2, 2, 3 }, { 5, 4, 3 }, { 6, 4, 5 } }; int n = sizeof(arr) / sizeof(Triangle); // Function Call cout << countUniqueTriangles(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;// Class to represent a Triangle// with three sides as a, b, cclass Triangle { int a, b, c; // Constructor public Triangle(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } // Function to check if two triangles are equal @Override public boolean equals(Object obj) { if (obj == this) return true; if (!(obj instanceof Triangle)) return false; Triangle t = (Triangle)obj; int cnt = 0; if ((this.a == t.a) || (this.a == t.b) || (this.a == t.c)) { cnt++; } if ((this.b == t.a) || (this.b == t.b) || (this.b == t.c)) { cnt++; } if ((this.c == t.a) || (this.c == t.b) || (this.c == t.c)) { cnt++; } // If all the three elements a, b, c // are same, triangle is not unique if (cnt == 3) { return false; } // For unique triangle return true return true; }}// Driver Classpublic class Main { // Function to count the number of // unique triangles public static int countUniqueTriangles(Triangle[] arr) { int n = arr.length; // Unique sets int uni = 0; for (int i = 0; i < n - 1; i++) { // Check on uniqueness for a // particular set w.r.t others int cnt = 0; for (int j = i; j < n - 1; j++) { // Checks if two triangles // are different if (arr[i].equals(arr[j + 1])) cnt++; } // If count of unique triangles // is same as the number of remaining // triangles then, increment count if (cnt == n - 1 - i) uni++; } // Since last element that // remains will be unique only return uni + 1; } // Main Function public static void main(String[] args) { // An array of objects of Triangle class to // store sides of Triangles Triangle[] arr = { new Triangle(3, 2, 2), new Triangle(3, 4, 5), new Triangle(1, 2, 2), new Triangle(2, 2, 3), new Triangle(5, 4, 3), new Triangle(6, 4, 5) }; // Function Call System.out.println(countUniqueTriangles(arr)); }} |
Python3
# Python3 program for the above approach# Structure to represent a Triangle# with three sides as a, b, cclass Triangle: def __init__(self, a, b, c): self.a = a self.b = b self.c = c # Function to overload relational # operator def __eq__(self, t): cnt = 0 if self.a in [t.a, t.b, t.c]: cnt += 1 if self.b in [t.a, t.b, t.c]: cnt += 1 if self.c in [t.a, t.b, t.c]: cnt += 1 # If all the three elements a, b, c # are same, triangle is not unique if cnt == 3: return False # For unique triangle, return True return True# Function returns the number# of unique Trianglesdef countUniqueTriangles(arr, n): # Unique sets uni = 0; for i in range(n - 1): # Check on uniqueness for a # particular set w.r.t others cnt = 0; for j in range(i, n - 1): # Checks if two triangles # are different if (arr[i] == arr[j + 1]): cnt += 1 # If count of unique triangles # is same as the number of remaining # triangles then, increment count if (cnt == n - 1 - i): uni+=1; # Since last element that # remains will be unique only return uni + 1;# Driver Code# An array of structure to# store sides of Trianglesarr = [ Triangle(3, 2, 2), Triangle(3, 4, 5), Triangle(1, 2, 2), Triangle(2, 2, 3), Triangle(5, 4, 3), Triangle(6, 4, 5) ] n = len(arr)# Function Callprint(countUniqueTriangles(arr, n))# This code is contributed by phasing17. |
C#
using System;// Structure to represent a Triangle// with three sides as a, b, cpublic struct Triangle{ public int a, b, c; // Function to overload relational // operator (==) public static bool operator ==(Triangle t1, Triangle t2) { int cnt = 0; if ((t1.a == t2.a) || (t1.a == t2.b) || (t1.a == t2.c)) { cnt++; } if ((t1.b == t2.a) || (t1.b == t2.b) || (t1.b == t2.c)) { cnt++; } if ((t1.c == t2.a) || (t1.c == t2.b) || (t1.c == t2.c)) { cnt++; } // If all the three elements a, b, c // are same, triangle is not unique if (cnt == 3) { return false; } // For unique triangle return true return true; } // Function to overload relational // operator (!=) public static bool operator !=(Triangle t1, Triangle t2) { return !(t1 == t2); }}// Class to hold the main programpublic class Program{ // Function returns the number // of unique Triangles public static int CountUniqueTriangles(Triangle[] arr, int n) { // Unique sets int uni = 0; for (int i = 0; i < n - 1; i++) { // Check on uniqueness for a // particular set w.r.t others int cnt = 0; for (int j = i; j < n - 1; j++) { // Checks if two triangles // are different if (arr[i] == arr[j + 1]) cnt++; } // If count of unique triangles // is same as the number of remaining // triangles then, increment count if (cnt == n - 1 - i) uni++; } // Since last element that // remains will be unique only return uni + 1; } // Main function public static void Main() { // An array of structure to // store sides of Triangles Triangle[] arr = { new Triangle { a = 3, b = 2, c = 2 }, new Triangle { a = 3, b = 4, c = 5 }, new Triangle { a = 1, b = 2, c = 2 }, new Triangle { a = 2, b = 2, c = 3 }, new Triangle { a = 5, b = 4, c = 3 }, new Triangle { a = 6, b = 4, c = 5 } }; int n = arr.Length; // Function Call Console.WriteLine(CountUniqueTriangles(arr, n)); }}// This code is contributed by divyansh2212 |
Javascript
// Class to represent a Triangleclass Triangle { constructor(a, b, c) { this.a = a; this.b = b; this.c = c; } // Function to overload relational operator equals(t) { let cnt = 0; if ([t.a, t.b, t.c].includes(this.a)) { cnt++; } if ([t.a, t.b, t.c].includes(this.b)) { cnt++; } if ([t.a, t.b, t.c].includes(this.c)) { cnt++; } // If all the three elements a, b, c // are same, triangle is not unique if (cnt === 3) { return false; } // For unique triangle, return True return true; }}// Function to count the number of unique trianglesfunction countUniqueTriangles(arr, n) { let uni = 0; for (let i = 0; i < n - 1; i++) { let cnt = 0; for (let j = i; j < n - 1; j++) { // Checks if two triangles are different if (arr[i].equals(arr[j + 1])) { cnt++; } } // If count of unique triangles is same as the number of remaining triangles // then, increment count if (cnt === n - 1 - i) { uni++; } } // Since the last element that remains will be unique only return uni + 1;}// Driver Code// An array of structure to store sides of Trianglesconst arr = [ new Triangle(3, 2, 2), new Triangle(3, 4, 5), new Triangle(1, 2, 2), new Triangle(2, 2, 3), new Triangle(5, 4, 3), new Triangle(6, 4, 5),];const n = arr.length;// Function Callconsole.log(countUniqueTriangles(arr, n)); |
Output
4
Time Complexity: O(N) Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
