Dado un entero positivo N , cuente el número de formas de escribir N como una suma de tres números. Para números que no son expresables, escriba -1.
Ejemplos:
Entrada: N = 4
Salida: 3
Explicación:
( 1 + 1 + 2 ) = 4
( 1 + 2 + 1 ) = 4
( 2 + 1 + 1 ) = 4.
Entonces, en total, hay 3 formas.
Entrada: N = 5
Salida: 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.
Entonces, en total, hay 6 formas
Enfoque: para resolver el problema mencionado anteriormente, si observamos más de cerca, observaremos un patrón en la solución de la pregunta. Para todos los números que son mayores que 2 obtenemos una serie 3, 6, 10, 15, 25 y así sucesivamente, que no es más que la suma de los primeros N-1 números naturales .
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(1)