All problems

Rod Triangle Lengths

Medium · two pointers

A craft shop sells wooden rods. The list lengths gives the length of each rod, and several rods may have the same length.

Three rods can be joined into a flat triangle when the two shorter ones add up to more than the longest one. A pair of rods that only just reaches the longest one (the sum is equal) does not make a triangle.

A customer wants a triangle whose three sides have three different lengths. Count how many different sets of three lengths {a, b, c} with a < b < c can make a triangle, using only lengths that appear in the list. It does not matter how many rods of a length the shop has, and a set is counted once however it is picked.

Examples

Example 1

Input: lengths = [3, 4, 5, 10]

Output: 1

Only {3, 4, 5} works: 3 + 4 > 5. Any set with 10 fails, because the other two lengths add up to at most 9.

Example 2

Input: lengths = [2, 2, 2, 2]

Output: 0

All four rods have the same length, so there is only one length and no set of three different lengths.

Example 3

Input: lengths = [2, 3, 4, 4, 5, 6]

Output: 7

The distinct lengths are 2, 3, 4, 5 and 6. The sets that work are {2, 3, 4}, {2, 4, 5}, {2, 5, 6}, {3, 4, 5}, {3, 4, 6}, {3, 5, 6} and {4, 5, 6}, seven in all.

Constraints