Count of ways to write N as a sum of three numbers
Given a positive integer N, count number of ways to write N as a sum of three numbers. For numbers which are not expressible print -1.
Examples:
Input: N = 4
Output: 3
Explanation:
( 1 + 1 + 2 ) = 4
( 1 + 2 + 1 ) = 4
( 2 + 1 + 1 ) = 4.
So in total, there are 3 ways.
Input: N = 5
Output: 6
( 1 + 1 + 3 ) = 5
( 1 + 3 + 1 ) = 5
( 3 + 1 + 1 ) = 5
( 1 + 2 + 2 ) = 5
( 2 + 2 + 1 ) = 5
( 2 + 1 + 2 ) = 5.
So in total, there are 6 ways
Approach: To solve the problem mentioned above if we take a closer look we will observe a pattern in solution to the question. For all the numbers that are greater than 2 we get a series 3, 6, 10, 15, 25 and so on, which is nothing but the sum of first N-1 natural numbers.
Below is the implementation of the above approach:
C++
// C++ program to count the total number of // ways to write N as a sum of three numbers #include <bits/stdc++.h> using namespace std; // Function to find the number of ways void countWays( int n) { // Check if number is less than 2 if (n <= 2) cout << "-1" ; else { // Calculate the sum int ans = (n - 1) * (n - 2) / 2; cout << ans; } } // Driver code int main() { int N = 5; countWays(N); return 0; } |
Java
// Java program to count the total number of // ways to write N as a sum of three numbers class GFG{ // Function to find the number of ways static void countWays( int n) { // Check if number is less than 2 if (n <= 2 ) { System.out.print( "-1" ); } else { // Calculate the sum int ans = (n - 1 ) * (n - 2 ) / 2 ; System.out.print(ans); } } // Driver code public static void main(String[] args) { int N = 5 ; countWays(N); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to count the total number of # ways to write N as a sum of three numbers def countWays(N): # Check if number is less than 2 if (N < = 2 ): print ( "-1" ) else : # Calculate the sum ans = (N - 1 ) * (N - 2 ) / 2 print (ans) # Driver code if __name__ = = '__main__' : N = 5 countWays(N) # This code is contributed by coder001 |
C#
// C# program to count the total number of // ways to write N as a sum of three numbers using System; class GFG{ // Function to find the number of ways static void countWays( int n) { // Check if number is less than 2 if (n <= 2) { Console.WriteLine( "-1" ); } else { // Calculate the sum int ans = (n - 1) * (n - 2) / 2; Console.WriteLine(ans); } } // Driver code static void Main() { int N = 5; countWays(N); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program to count the total number of // ways to write N as a sum of three numbers // Function to find the number of ways function countWays(n) { // Check if number is less than 2 if (n <= 2) document.write( "-1" ); else { // Calculate the sum var ans = (n - 1) * (n - 2) / 2; document.write( ans); } } // Driver code var N = 5; countWays(N); </script> |
6
Time Complexity: O(1)
Auxiliary Space: O(1) as constant space for variables is being used
Contact Us