Stack Overflow Asked by Etoile on December 12, 2020

I need to find all possible triangles in a set of integers. I successfully got the result, but I have many duplicates, for example:

A(3, 3, 4) == B(4, 3, 3)

I don’t need to find similar triangles, I need to know when they are equal.

I tried to save my triangles as structs and wanted to compare them:

```
struct triangle
{
int a;
int b; // I stored all found triangles this way
int c;
};
int getNumberOfDuplicates(struct triangle savedTriangles[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int a,b,c,x,y,z;
if (i != j) {
a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;
if (areTheSame) { // Here I don't know how to compare them
count++;
}
}
}
}
return count;
```

Is there any mathematical way to compare them? Or any programming way?

The simplest solution would be to sort the three numbers.

```
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void bubble_sort(int *a, int *b, int *c) {
if (a > b) swap(&a, &b);
if (b > c) swap(&b, &c);
if (a > b) swap(&a, &b);
}
```

At which point it should be trivial to compare if they are equal.

Correct answer by Bill Lynch on December 12, 2020

Assuming the list is complete, every triangle will be repeated for every permutation of its sides `a, b, c`

. Therefore each triangle is a duplicate of one with `a <= b <= c`

, so it is enough to only check those, and automatically count any triangle with `b < a`

or `c < b`

as a duplicate.

```
int getNumberOfDuplicates(struct triangle savedTriangles[], int size){
int count = 0;
for (int i = 0; i < size; i++){
int a = savedTriangles[i].a,
b = savedTriangles[i].b,
c = savedTriangles[i].c;
if(b < a || c < b){
count++;
continue;
}
for (int j = i + 1; j < size; j++){
int x = savedTriangles[j].a,
y = savedTriangles[j].b,
z = savedTriangles[j].c;
if(a == x && b == y && c == z){
count++;
break;
}
}
}
return count;
}
```

Answered by dxiv on December 12, 2020

You have to do two modifications to your code:

- Just compare a triangle to the followers only, you are now counting it twice, which will give you double the desired result.
- Sort the lengths in ascending order by using
`min`

and`max`

, then compare them.

So your code should look like this:

```
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) { //Start from i + 1 not 0
int a, b, c, x, y, z, a1, b1, c1, x1, y1, z1;
a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;
a1 = min(a, min(b, c));
c1 = max(a, max(b, c));
b1 = a + b + c - a1 - c1;
x1 = min(x, min(y, z));
z1 = max(x, max(y, z));
y1 = x + y + z - x1 - z1;
if (a1 == x1 && b1 == y1 && c1 == z1)
count++;
}
}
int min (int a, int b)
{
return a < b ? a : b;
}
int max (int a, int b)
{
return a > b ? a : b;
}
```

There is a mathematical way by getting their sum, product and sum of their squares without the need to sort them, any triplet will give a unique set of results regardless of their order according to this, so the alternative code should look like this:

```
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
int a, b, c, x, y, z, s1, s2, ss1, ss2, p1, p2;
a = savedTriangles[i].a; b = savedTriangles[i].b; c = savedTriangles[i].c;
x = savedTriangles[j].a; y = savedTriangles[j].b; z = savedTriangles[j].c;
s1 = a + b + c;
ss1 = a * a + b * b + c * c;
p1 = a * b * c;
s2 = x + y + c;
ss2 = x * x + y * y + z * z;
p2 = x * y * z;
if (s1 == s2 && ss1 == ss2 && p1 == p2)
count++;
}
}
```

Answered by AbdelAziz AbdelLatef on December 12, 2020

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP