Count the number of possible triangles ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

Asked in AMAZON and MICROSOFT


Given an unsorted array arr[] of n positive integers. Find the number of triangles that can be formed with three different array elements as lengths of three sides of triangles. 

Example 1:

Input: 
n = 3
arr[] = {3, 5, 4}
Output: 
1
Explanation: 
A triangle is possible 
with all the elements 5, 3 and 4.

Example 2:

Input: 
n = 5
arr[] = {6, 4, 9, 7, 8}
Output: 
10
Explanation: 
There are 10 triangles
possible  with the given elements like
(6,4,9), (6,7,8),...

 

Your Task: 
This is a function problem. You only need to complete the function findNumberOfTriangles() that takes arr[] and n as input parameters and returns the count of total possible triangles.



Expected Time Complexity: O(n2).
Expected Space Complexity: O(1).

Constraints:
3 <= n <= 103

1 <= arr[i] <= 103


Code:

#include <bits/stdc++.h>

using namespace std;


// Function to count all possible

// triangles with arr[] elements

int findNumberOfTriangles(int arr[], int n)

{

    // Count of triangles

    int count = 0;


    // The three loops select three

    // different values from array

    for (int i = 0; i < n; i++) {

        for (int j = i + 1; j < n; j++) {

// The innermost loop checks for

            // the triangle property

            for (int k = j + 1; k < n; k++)


                // Sum of two sides is greater

                // than the third

                if (

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

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

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

                    count++;

        }

    }

    return count;

}


// Driver code

int main()

{

int arr[] = { 10, 21, 22, 100, 101, 200, 300 };

    int size = sizeof(arr) / sizeof(arr[0]);


    cout

        << "Total number of triangles possible is "

        << findNumberOfTriangles(arr, size);


    return 0;

}








Previous
Next Post »