Contar formas de expresar un número como suma de números consecutivos

Dado un número entero N , la tarea es encontrar el número de formas de representar este número como una suma de 2 o más números naturales consecutivos .

Ejemplos: 
 

Entrada: N = 15 
Salida: 3 
Explicación: 
15 se puede representar como: 
 

1. 1 + 2 + 3 + 4 + 5
2. 4 + 5 + 6
3. 7 + 8

Entrada: N = 10 
Salida: 1 
 

Enfoque: La idea es representar N como una secuencia de longitud L+1 como: 
N = a + (a+1) + (a+2) + .. + (a+L) 
=> N = (L+1 )*a + (L*(L+1))/2 
=> a = (N- L*(L+1)/2)/(L+1) 
Sustituimos los valores de L desde 1 hasta L* (L+1)/2 < N 
Si obtenemos ‘a’ como un número natural, entonces la solución debe contarse.
 

?list=PLM68oyaqFM7Q-sv3gA5xbzfgVkoQ0xDrW
 

// C++ program to count number of ways to express
// N as sum of consecutive numbers.
#include <bits/stdc++.h>
using namespace std;
 
long int countConsecutive(long int N)
{
    // constraint on values of L gives us the
    // time Complexity as O(N^0.5)
    long int count = 0;
    for (long int L = 1; L * (L + 1) < 2 * N; L++) {
        double a = (1.0 * N - (L * (L + 1)) / 2) / (L + 1);
        if (a - (int)a == 0.0)
            count++;
    }
    return count;
}
 
// Driver Code
int main()
{
    long int N = 15;
    cout << countConsecutive(N) << endl;
    N = 10;
    cout << countConsecutive(N) << endl;
    return 0;
}

// A Java program to count number of ways
// to express N as sum of consecutive numbers.
public class SumConsecutiveNumber {
    // Utility method to compute number of ways
    // in which N can be represented as sum of
    // consecutive number
    static int countConsecutive(int N)
    {
        // constraint on values of L gives us the
        // time Complexity as O(N^0.5)
        int count = 0;
        for (int L = 1; L * (L + 1) < 2 * N; L++) {
            double a = (double)((1.0 * N - (L * (L + 1)) / 2) / (L + 1));
            if (a - (int)a == 0.0)
                count++;
        }
        return count;
    }
 
    // Driver code to test above function
    public static void main(String[] args)
    {
        int N = 15;
        System.out.println(countConsecutive(N));
        N = 10;
        System.out.println(countConsecutive(N));
    }
}
// This code is contributed by Sumit Ghosh

# Python program to count number of ways to
# express N as sum of consecutive numbers.
 
def countConsecutive(N):
     
    # constraint on values of L gives us the
    # time Complexity as O(N ^ 0.5)
    count = 0
    L = 1
    while( L * (L + 1) < 2 * N):
        a = (1.0 * N - (L * (L + 1) ) / 2) / (L + 1)
        if (a - int(a) == 0.0):
            count += 1
        L += 1
    return count
 
# Driver code
 
N = 15
print (countConsecutive(N))
N = 10
print (countConsecutive(N))
 
# This code is contributed by Sachin Bisht

// A C# program to count number of
// ways to express N as sum of
// consecutive numbers.
using System;
 
public class GFG {
 
    // Utility method to compute
    // number of ways in which N
    // can be represented as sum
    // of consecutive number
    static int countConsecutive(int N)
    {
 
        // constraint on values of L
        // gives us the time
        // Complexity as O(N^0.5)
        int count = 0;
        for (int L = 1; L * (L + 1)
                        < 2 * N;
             L++) {
            double a = (double)((1.0
                                   * N
                               - (L * (L + 1))
                                     / 2)
                              / (L + 1));
 
            if (a - (int)a == 0.0)
                count++;
        }
 
        return count;
    }
 
    // Driver code to test above
    // function
    public static void Main()
    {
        int N = 15;
        Console.WriteLine(
            countConsecutive(N));
 
        N = 10;
        Console.Write(
            countConsecutive(N));
    }
}
 
// This code is contributed by
// nitin mittal.

<?php
// PHP program to count number
// of ways to express N as sum
// of consecutive numbers.
 
function countConsecutive($N)
{
    // constraint on values
    // of L gives us the
    // time Complexity as O(N^0.5)
    $count = 0;
    for ($L = 1;
         $L * ($L + 1) < 2 * $N; $L++)
    {
        $a = (int)(1.0 * $N - ($L *
             (int)($L + 1)) / 2) / ($L + 1);
        if ($a - (int)$a == 0.0)
            $count++;
    }
    return $count;
}
 
// Driver Code
$N = 15;
echo countConsecutive($N), "\n";
$N = 10;
echo countConsecutive($N), "\n";
 
// This code is contributed by ajit
?>

<script>
    // A Javascript program to count number of
    // ways to express N as sum of
    // consecutive numbers.
     
    // Utility method to compute
    // number of ways in which N
    // can be represented as sum
    // of consecutive number
    function countConsecutive(N)
    {
           
        // constraint on values of L
        // gives us the time
        // Complexity as O(N^0.5)
        let count = 0;
        for (let L = 1; L * (L + 1) < 2 * N; L++)
        {
            let a = ((1.0 * N-(L * (L + 1)) / 2) / (L + 1));
                        
            if (a - parseInt(a, 10) == 0.0)
                count++;    
        }
           
        return count;
    }
     
    let N = 15;
    document.write(countConsecutive(N) + "</br>");
 
    N = 10;
    document.write(countConsecutive(N));
     
</script>

3
1

Complejidad del tiempo: O(N^0.5)

Espacio Auxiliar : O(1)

Este artículo es una contribución de Pranav Marathe . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.