Count non-negative triplets with sum equal to N
Given an integer N. The task is to find the number of different ordered triplets(a, b, c) of non-negative integers such that a + b + c = N .
Examples:
Input : N = 2
Output : 6
Triplets are : (0, 0, 2), (1, 0, 1), (0, 1, 1), (2, 0, 0), (0, 2, 0), (1, 1, 0)
Input : N = 50
Output : 1326
Naive Approach:
We can use three nested loops to generate all possible ordered triplets of non-negative integers such that their sum is equal to the given number N.
Implementation of the above approach:
C++
#include <iostream> using namespace std; // Function to calculate number of triplets int countTriplets( int N) { // Initializing result int res = 0; // Finding all possible combinations // using nested loops for ( int i = 0; i <= N; i++) { for ( int j = 0; j <= N; j++) { for ( int k = 0; k <= N; k++) { if (i + j + k == N) res++; } } } // Returning result return res; } // Driver code int main() { int N = 50; // Function call cout << countTriplets(N); return 0; } |
Java
import java.util.Scanner; public class Main { // Function to calculate number of triplets public static int countTriplets( int N) { // Initializing result int res = 0 ; // Finding all possible combinations // using nested loops for ( int i = 0 ; i <= N; i++) { for ( int j = 0 ; j <= N; j++) { for ( int k = 0 ; k <= N; k++) { if (i + j + k == N) res++; } } } // Returning result return res; } // Driver code public static void main(String[] args) { int N = 50 ; // Function call System.out.println(countTriplets(N)); } } // This code is contributed by Prajwal Kandekar |
Python3
def countTriplets(N): # Initializing result res = 0 # Finding all possible combinations # using nested loops for i in range (N + 1 ): for j in range (N + 1 ): for k in range (N + 1 ): if i + j + k = = N: res + = 1 # Returning result return res # Driver code N = 50 # Function call print (countTriplets(N)) # This code is contributed by Prajwal Kandekar |
C#
using System; public class GFG{ // Function to calculate number of triplets public static int CountTriplets( int N) { // Initializing result int res = 0; // Finding all possible combinations // using nested loops for ( int i = 0; i <= N; i++) { for ( int j = 0; j <= N; j++) { for ( int k = 0; k <= N; k++) { if (i + j + k == N) res++; } } } // Returning result return res; } // Driver code public static void Main( string [] args) { int N = 50; // Function call Console.WriteLine(CountTriplets(N)); } } |
Javascript
// Function to calculate number of triplets function countTriplets(N) { // Initializing result let res = 0; // Finding all possible combinations // using nested loops for (let i = 0; i <= N; i++) { for (let j = 0; j <= N; j++) { for (let k = 0; k <= N; k++) { if (i + j + k == N) res++; } } } // Returning result return res; } // Driver code let N = 50; // Function call console.log(countTriplets(N)); |
1326
Time Complexity: O(N^3)
Auxiliary Space: O(1)
Efficient Approach :
First, it is easy to see that for each non-negative integer N, the equation a + b = N can be satisfied by (N+1) different ordered pairs of (a, b). Now we can assign c values from 0 to N then the ordered pairs for a+b can be found. It will form a series of N+1 natural numbers and its sum will give the count of triplets.
Below is the implementation of the above approach :
C++
// CPP program to find triplets count #include <bits/stdc++.h> using namespace std; // Function to find triplets count int triplets( int N) { // Sum of first n+1 natural numbers return ((N + 1) * (N + 2)) / 2; } // Driver code int main() { int N = 50; // Function call cout << triplets(N); return 0; } |
Java
// Java program to find triplets count class GFG { // Function to find triplets count static int triplets( int N) { // Sum of first n+1 natural numbers return ((N + 1 ) * (N + 2 )) / 2 ; } // Driver code public static void main(String[] args) { int N = 50 ; System.out.println(triplets(N)); } } // This code is contributed // by PrinciRaj1992 |
Python3
# Python3 program to find triplets count # Function to find triplets count def triplets(N): # Sum of first n+1 natural numbers return ((N + 1 ) * (N + 2 )) / / 2 ; # Driver code N = 50 ; # Function call print (triplets(N)) # This code is contributed by nidhi |
C#
// C# program to find triplets count using System; class GFG { // Function to find triplets count static int triplets( int N) { // Sum of first n+1 natural numbers return ((N + 1) * (N + 2)) / 2; } // Driver code public static void Main() { int N = 50; Console.WriteLine(triplets(N)); } } // This code is contributed // by anuj_67.. |
Javascript
<script> // Javascript program to find triplets count // Function to find triplets count function triplets(N) { // Sum of first n+1 natural numbers return ((N + 1) * (N + 2)) / 2; } let N = 50; document.write(triplets(N)); </script> |
1326
Time Complexity : O(1)
Auxiliary Space: O(1)
Contact Us