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 waysvoid 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 codeint 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 numbersclass GFG{// Function to find the number of waysstatic 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 codepublic 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 numbersdef 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 waysfunction 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 codevar N = 5;countWays(N);</script> |
6
Time Complexity: O(1)
Auxiliary Space: O(1) as constant space for variables is being used
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
