# Find Number of Triangles With The Same Perimeter

by Bittle in Programming Help

# Problem

Given a perimeter p, find the number of triangles that have sides a, b, and c that add up to p. Make sure to not repeat triangles, e.g 0, 0, 9 = 9, 0, 0 (same triangle but flipped).

# Solution

For a faster run time, and to avoid duplicates, sort the sides from smallest to greatest (9, 5, 6 will become 5, 6, 9). We don't need to check all possibilities since a + b + c = p, and an equilateral triangle means a = b = c, so therefore, we only need to check from 0 to p/3 for one side. A 2D array is used to make search easier and faster. Variable a will represent the rows, b the columns, and c the contents inside [a][b].

# Code (java)

``````import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.print("Enter perimeter: ");
int p = scanner.nextInt();
int[][] mat = new int[p / 3 + 1][p / 2 + 1];

for (int i = 0; i < mat.length; i++) {
for (int i1 = 0; i1 < mat[i].length; i1++) {
mat[i][i1] = -1;
}
}

//printMat(mat);

scanner.close();

int num = 0;

for (int a = 0; a < p/3 + 1; a++) {

for (int b = 0; b + a < p + 1; b++) {
int c = p - (a + b);

// sort (to hash)
int a1 = smallest(a, b, c);
int b1;
int c1 = biggest(a, b, c);

if (a1 == a) {
b1 = min(b, c);
} else if (a1 == b) {
b1 = min(a, c);
} else {
b1 = min(a, b);
}

if (mat[a1][b1] == -1) {
num++;
mat[a1][b1] = c1;
System.out.println("a: " + a1 + ", b: " + b1 + ", c: " + c1);
}
}

}

System.out.println("TOTAL: " + num);
printMat(mat);
}

private static void printMat(int[][] mat) {
System.out.println("Printing matrix...");
for (int[] ints : mat) {
for (int anInt : ints) {
System.out.printf("%-5s", (anInt == -1) ? "" : anInt);
}

System.out.println();
}
}

private static int smallest(int a1, int b1, int c1) {
return min(a1, min(b1, c1));
}

private static int biggest(int a1, int b1, int c1) {
return max(a1, max(b1, c1));
}

private static int min(int a1, int b1) {
if (a1 < b1)
return a1;
return b1;
}

private static int max(int a1, int b1) {
if (a1 > b1)
return a1;
return b1;
}
}
``````

# Output

``````Enter perimeter: 9
a: 0, b: 0, c: 9
a: 0, b: 1, c: 8
a: 0, b: 2, c: 7
a: 0, b: 3, c: 6
a: 0, b: 4, c: 5
a: 1, b: 1, c: 7
a: 1, b: 2, c: 6
a: 1, b: 3, c: 5
a: 1, b: 4, c: 4
a: 2, b: 2, c: 5
a: 2, b: 3, c: 4
a: 3, b: 3, c: 3
TOTAL: 12
Printing matrix...
9  8  7  6  5
7  6  5  4
5  4
3
``````