Given an integer N, the task is to find the number of ways to split N into ordered triplets which can together form a triangle.
Examples:
Input: N = 15
Output: Total number of triangles possible are 28Input: N = 9
Output: Total number of triangles possible is 10
Approach: The following observation needs to be made in order to solve the problem:
If N is split into 3 integers a, b and c, then the following conditions need to be satisfied for a, b and c to form a triangle:
- a + b > c
- a + c > b
- b + c > a
Therefore, iterate over the range [1, N] using nested loops to generate triplets, and for each triplet check if it forms a triangle or not.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to return the // required number of ways int Numberofways( int n) { int count = 0; for ( int a = 1; a < n; a++) { for ( int b = 1; b < n; b++) { int c = n - (a + b); // Check if a, b and c can // form a triangle if (a + b > c && a + c > b && b + c > a) { count++; } } } // Return number of ways return count; } // Driver Code int main() { int n = 15; cout << Numberofways(n) << endl; return 0; } |
Java
// Java Program to implement // the above approach import java.io.*; class GFG { // Function to return the // required number of ways static int Numberofways( int n) { int count = 0 ; for ( int a = 1 ; a < n; a++) { for ( int b = 0 ; b < n; b++) { int c = n - (a + b); // Check if a, b, c can // form a triangle if (a + b > c && a + c > b && b + c > a) { count++; } } } return count; } // Driver Code public static void main(String[] args) { int n = 15 ; System.out.println(Numberofways(n)); } } |
Python3
# Python Program to implement # the above approach # Function to return the # required number of ways def Numberofways(n): count = 0 for a in range ( 1 , n): for b in range ( 1 , n): c = n - (a + b) # Check if a, b, c can form a triangle if (a < b + c and b < a + c and c < a + b): count + = 1 return count # Driver code n = 15 print (Numberofways(n)) |
C#
// C# Program to implement // the above approach using System; class GFG { // Function to return the // required number of ways static int Numberofways( int n) { int count = 0; for ( int a = 1; a < n; a++) { for ( int b = 1; b < n; b++) { int c = n - (a + b); // Check if a, b, c can form // a triangle or not if (a + b > c && a + c > b && b + c > a) { count++; } } } // Return number of ways return count; } // Driver Code static public void Main() { int n = 15; Console.WriteLine(Numberofways(n)); } } |
Javascript
<script> // Javascript Program to implement // the above approach // Function to return the // required number of ways function Numberofways(n) { var count = 0; for ( var a = 1; a < n; a++) { for ( var b = 1; b < n; b++) { var c = n - (a + b); // Check if a, b and c can // form a triangle if (a + b > c && a + c > b && b + c > a) { count++; } } } // Return number of ways return count; } // Driver Code var n = 15; document.write( Numberofways(n)); // This code is contributed by noob2000. </script> |
28
Time Complexity: O(N2)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!