Clash Royale CLAN TAG#URR8PPP

Number of possible triangles given an array of numbers question

I'm trying to find the number of possible triangles that can be formed with set of numbers here:

https://www.geeksforgeeks.org/find-number-of-triangles-possible/

I've written the javaScript version of it. however, I don't really understand one part of the solution:

// Total number of possible triangles that can
// be formed with the two fixed elements is
// k - j - 1. The two fixed elements are arr[i]
// and arr[j]. All elements between arr[j+1]/ to
// arr[k-1] can form a triangle with arr[i] and arr[j].
// One is subtracted from k because k is incremented
// one extra in above while loop.
// k will always be greater than j. If j becomes equal
// to k, then above loop will increment k, because arr[k]
// + arr[i] is always greater than arr[k]


Problem:

I still don't get this logic. How did k-j come into the picture?

k-j

How is that number of triangles that can be formed with arr[i], arr[j] and arr[k] (with arr[i] < arr[j] < arr[k]) give count as k-j I'm kinda unclear on this part.

k-j

Can someone enlighten me?

JS solution for the problem:

var triangleNumber = function(arr)
let count = 0, n = arr.length;

//Sort the array in ascending order.
arr.sort((a,b) => return a-b; );

// Set three pointers, i, j = i+1 and k=i+2
for(let i=0; i<n-2; i++)
let k = i+2;
for(let j=i+1; j<n; j++)
// If sum of two sides > third side
/* Find the rightmost element which is smaller
than the sum of two fixed elements
The important thing to note here is, we use
the previous value of k. If value of arr[i] +
arr[j-1] was greater than arr[k], then arr[i] +
arr[j] must be greater than k, because the
array is sorted. */
while (k <n && arr[i] + arr[j] > arr[k])
++k;


/* Total number of possible triangles that can be
formed with the two fixed elements is k - j - 1.
The two fixed elements are arr[i] and arr[j]. All
elements between arr[j+1] to arr[k-1] can form a
triangle with arr[i] and arr[j]. One is subtracted
from k because k is incremented one extra in above
while loop. k will always be greater than j. If j
becomes equal to k, then above loop will increment
k, because arr[k] + arr[i] is always/ greater than
arr[k] */
count += k-j-1;



return count<0? 0: count;
;

const arr = [2,2,3,4];
console.log(triangleNumber(arr));

k-j

Fix ‘i’ and ‘j’ and find the rightmost index ‘k’ (or largest ‘arr[k]’) such that ‘arr[i] + arr[j] > arr[k]’. The number of triangles that can be formed with ‘arr[i]’ and ‘arr[j]’ as two sides is ‘k – j’. Add ‘k – j’ to count of triangles.

1 Answer
1

There are k-j elements starting from the element after j to element k. All of them are valid third sides of the triangle with arr[i] and arr[j] as the first two sides.

k-j

j

k

arr[i]

arr[j]

E.g. if the first two sides are arr[2] and arr[4], and the highest k where arr[i] + arr[j] > arr[k] is 10, you can make a triangle with k = 5, 6, 7, 8, 9, or 10. There are 6 indexes there, and 10 - 4 = 6.

arr[2]

arr[4]

k

arr[i] + arr[j] > arr[k]

10

k = 5, 6, 7, 8, 9, or 10

10 - 4 = 6

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.