Divide el número en tres partes.

Posted on by Rudeus Greyrat

Dado un número realmente grande, divídalo en 3 números enteros de modo que sumen el número original y cuente varias formas de hacerlo.

Ejemplos: 

Input : 3
Output : 10
The possible combinations where the sum
of the numbers is equal to 3 are:
0+0+3 = 3
0+3+0 = 3
3+0+0 = 3
0+1+2 = 3
0+2+1 = 3
1+0+2 = 3
1+2+0 = 3
2+0+1 = 3
2+1+0 = 3
1+1+1 = 3

Input : 6
Output : 28

Un total de 10 formas, por lo que la respuesta es 10. 

Enfoque ingenuo: pruebe todas las combinaciones desde 0 hasta el número dado y verifique si suman el número dado o no, si lo hacen, aumente el conteo en 1 y continúe el proceso. 

C++

// C++ program to count number of ways to break
// a number in three parts.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to count number of ways
// to make the given number n
ll count_of_ways(ll n)
{
    ll count = 0;
    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)
                    count++;
    return count;
}
 
// Driver Function
int main()
{
    ll n = 3;
    cout << count_of_ways(n) << endl;
    return 0;
}

Java

// Java program to count number of ways to break
// a number in three parts
import java.io.*;
 
class GFG {
    // Function to count number of ways
    // to make the given number n
    static long count_of_ways(long n)
    {
        long count = 0;
        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)
                        count++;
        return count;
    }
 
    // driver program
    public static void main(String[] args)
    {
        long n = 3;
        System.out.println(count_of_ways(n));
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python3 program to count number of
# ways to break
# a number in three parts.
 
# Function to count number of ways
# to make the given number n
def count_of_ways(n):
 
    count = 0
    for i in range(0, n+1):
        for j in range(0, n+1):
            for k in range(0, n+1):
                if(i + j + k == n):
                    count = count + 1
    return count
 
# Driver Function
if __name__=='__main__':
    n = 3
    print(count_of_ways(n))
 
 
# This code is contributed by
# Sanjit_Prasad

C#

// C# program to count number of ways
// to break a number in three parts
using System;
 
class GFG {
     
    // Function to count number of ways
    // to make the given number n
    static long count_of_ways(long n)
    {
        long count = 0;
        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)
                        count++;
        return count;
    }
 
    // driver program
    public static void Main()
    {
        long n = 3;
        Console.WriteLine(count_of_ways(n));
    }
}
 
// This code is Contributed by vt_m.

PHP

<?php
// PHP program to count number
// of ways to break a number
// in three parts.
 
// Function to count number of ways
// to make the given number n
function count_of_ways( $n)
{
    $count = 0;
    for ($i = 0; $i <= $n; $i++)
        for ($j = 0; $j <= $n; $j++)
            for ($k = 0; $k <= $n; $k++)
                if ($i + $j + $k == $n)
                    $count++;
    return $count;
}
 
// Driver Code
$n = 3;
echo count_of_ways($n);
 
// This code is Contributed by vt_m.
?>

Javascript

<script>
 
// JavaScript program to count
// number of ways to break
// a number in three parts.
 
// Function to count number of ways
// to make the given number n
function count_of_ways(n)
{
    let count = 0;
    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)
                    count++;
                     
    return count;
}
 
// Driver code
let n = 3;
 
document.write(count_of_ways(n) + "<br>");
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción : 

10

Complejidad del tiempo : O(n 3 ) 

Enfoque eficiente: si observamos cuidadosamente los casos de prueba, nos damos cuenta de que la cantidad de formas de dividir un número n en 3 partes es igual a (n+1) * (n+2) / 2. 

C++

// C++ program to count number of ways to break
// a number in three parts.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to count number of ways
// to make the given number n
ll count_of_ways(ll n)
{
    ll count;
    count = (n + 1) * (n + 2) / 2;
    return count;
}
 
// Driver Function
int main()
{
    ll n = 3;
    cout << count_of_ways(n) << endl;
    return 0;
}

Java

// Java program to count number of ways to break
// a number in three parts
import java.io.*;
 
class GFG {
    // Function to count number of ways
    // to make the given number n
    static long count_of_ways(long n)
    {
        long count = 0;
        count = (n + 1) * (n + 2) / 2;
        return count;
    }
 
    // driver program
    public static void main(String[] args)
    {
        long n = 3;
        System.out.println(count_of_ways(n));
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python 3 program to count number of
# ways to break a number in three parts.
 
# Function to count number of ways
# to make the given number n
def count_of_ways(n):
    count = 0
    count = (n + 1) * (n + 2) // 2
    return count
 
# Driver code
n = 3
print(count_of_ways(n))
 
# This code is contributed by Shrikant13

C#

// C# program to count number of ways to
// break a number in three parts
using System;
 
class GFG {
     
    // Function to count number of ways
    // to make the given number n
    static long count_of_ways(long n)
    {
        long count = 0;
        count = (n + 1) * (n + 2) / 2;
        return count;
    }
 
    // driver program
    public static void Main()
    {
        long n = 3;
        Console.WriteLine(count_of_ways(n));
    }
}
 
// This code is Contributed by vt_m.

PHP

<?php
// PHP program to count number
// of ways to break a number
// in three parts.
 
// Function to count number of ways
// to make the given number n
function count_of_ways( $n)
{
    $count;
    $count = ($n + 1) * ($n + 2) / 2;
    return $count;
}
 
// Driver Code
$n = 3;
echo count_of_ways($n);
 
// This code is Contributed by vt_m.
?>

Javascript

<script>
 
// javascript program to count number of ways to
// break a number in three parts
 
      
    // Function to count number of ways
    // to make the given number n
     
    function count_of_ways(n)
    {
        var count = 0;
        count = (n + 1) * (n + 2) / 2;
        return count;
    }
  
    // driver program
 
        var n = 3;
        document.write(count_of_ways(n));
 
// This code is contributed by bunnyram19.
</script>

Producción : 

10

Complejidad de tiempo: O(1)

 Este artículo es una contribución de Aditya Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *