Find all triplets which satisfy triangle property c++
Answers
Answer:
C program for no.Of days remaining in a year for the given date and month of a year
import java.util.*;
public class TriangleFinder {
public static void main(String[] args) {
int[] potentialEdges = { 1, 2, 3, 4, 5, 6, 7 };
int n = potentialEdges.length;
HashSet<String> triangles = new HashSet<String>();
Arrays.sort(potentialEdges);
for (int aIndex = 0; aIndex < n; aIndex++) {
for (int bIndex = 0; bIndex < n; bIndex++) {
if (aIndex == bIndex) {
continue;
}
int a = potentialEdges[aIndex];
int b = potentialEdges[bIndex];
// Condition 1: a + b > c
int i = 0;
int j = indexOfLesser(potentialEdges, 0, n - 1, a + b);
if (j == -1) {
continue;
}
// Condition 2: a + c > b
i = indexOfGreater(potentialEdges, i, j, b - a);
if (i == -1)
{
continue;
}
// Condition 3: b + c > a
i = indexOfGreater(potentialEdges, i, j, a - b);
if (i == -1) {
continue;
}
// At this point, we have the solutions for the current value of `a` and `b`.
// The subproblem is already solved at this point. Iterating below increases
// the time complexity of the solution but is a necessary evil if we want to
// output the answer.
for (int cIndex = i; cIndex <= j; cIndex++) {
int c = potentialEdges[cIndex];
if (aIndex == cIndex || bIndex == cIndex) {
continue;
}
// Let's sort `a`, `b`, and `c` and then put them in a hash set to remove duplicate answers
int[] combo = new int[] { a, b, c };
Arrays.sort(combo);
String comboString = "<" + combo[0] + ", " + combo[1] + ", " + combo[2] + ">";
triangles.add(comboString);
}
}
}
for (String triangle : triangles)
{
System.out.println(triangle);
}
}
private static int indexOfGreater(int[] array, int startIndex, int endIndex, int findValue) {
int initialEndIndex = endIndex;
while (endIndex >= startIndex) {
int midIndex = midpoint(startIndex, endIndex);
int midValue = array[midIndex];
if (midValue <= findValue) {
startIndex = midIndex + 1;
} else {
endIndex = midIndex - 1;
}
}
return (startIndex <= initialEndIndex) ? startIndex : -1;
}
private static int indexOfLesser(int[] array, int startIndex, int endIndex, int findValue) {
int initialStartIndex = startIndex;
while (endIndex >= startIndex) {
int midIndex = midpoint(startIndex, endIndex);
int midValue = array[midIndex];
if (midValue < findValue) {
startIndex = midIndex + 1;
} else {
endIndex = midIndex - 1;
}
}
return (endIndex >= initialStartIndex) ? endIndex : -1;
}
private static int midpoint(int low, int high) {
return low + (high - low) / 2;
}
}