Comprobar si un número se puede expresar como una suma de números consecutivos

Dado un número n, la tarea es comprobar si se puede expresar como una suma de dos o más números consecutivos o no. 
Ejemplos: 
 

Input  : n = 10 
Output : true
It can be expressed as sum of two consecutive
numbers 1 + 2 + 3 + 4.

Input  : n = 16  
Output : false
It cannot be expressed as sum of two consecutive
numbers.

Input  : n = 5  
Output : true
2 + 3 = 5

Hay un método directo y rápido para resolver esto. Si un número es una potencia de dos, entonces no se puede expresar como una suma de números consecutivos, de lo contrario, sí.
La idea se basa en los siguientes dos hechos. 
1) La suma de dos números consecutivos es impar ya que uno de ellos tiene que ser par y el otro impar. 
2) 2 ⁿ = 2 ^n-1 + 2 ^n-1
Si observamos más de cerca 1) y 2), podemos obtener la intuición detrás del hecho.
A continuación se muestra la implementación de la idea anterior. 
 

// C++ program to check if a number can
// be expressed as sum of consecutive numbers
#include<bits/stdc++.h>
using namespace std;
  
// This function returns true if n can be
// expressed sum of consecutive.
bool canBeSumofConsec(unsigned int n)
{
    // We basically return true if n is a
    // power of two
    return ((n&(n-1)) && n);
}
  
// Driver code
int main()
{
    unsigned int n = 15;
    canBeSumofConsec(n)? cout << "true" :
                         cout << "false";
    return 0;
}

// Java program to check if a number can
// be expressed as sum of consecutive numbers
  
class Test
{
    // This function returns true if n can be
    // expressed sum of consecutive.
    static boolean canBeSumofConsec(int n)
    {
        // We basically return true if n is a
        // power of two
        return (((n&(n-1))!=0) && n!=0);
    }
      
    // Driver method
    public static void main(String[] args) 
    {
        int n = 15;
        System.out.println(canBeSumofConsec(n) ? "true" : "false");
    }
}

# Python 3 program to check if a number can
# be expressed as sum of consecutive numbers
  
  
# This function returns true if n 
# can be expressed sum of consecutive.
def canBeSumofConsec(n) :
  
    # We basically return true if n is a
    # power of two
    return ((n&(n-1)) and n)
  
  
# Driver code
n = 15
if(canBeSumofConsec(n)) :
    print("true")
else :
    print("false")
      
# This code is contributed by Nikita Tiwari.

// C# program to check if a number can be
// expressed as sum of consecutive numbers
using System;
  
class Test
{
    // This function returns true if n
    // can be expressed sum of consecutive.
    static bool canBeSumofConsec(int n)
    {
        // We basically return true if n is a
        // power of two
        return (((n & (n - 1)) != 0) && n != 0);
    }
      
    // Driver Code
    public static void Main() 
    {
        int n = 15;
        Console.Write(canBeSumofConsec(n) ? "True" : "False");
    }
}
  
// This code is contributed by Nitin Mittal.

<?php
// php program to check if a number
// can be expressed as sum of 
// consecutive numbers
  
// This function returns true if n
// can be expressed sum of consecutive.
function canBeSumofConsec($n)
{
      
    // We basically return true if n is a
    // power of two
    return (($n & ($n - 1)) && $n);
}
  
// Driver code
    $n = 15;
    if(canBeSumofConsec($n)) 
        echo "true" ;
    else
        echo "false";
  
// This code is contributed by
// nitin mittal. 
?>

<script>
  
// Javascript program to check if a number can
// be expressed as sum of consecutive numbers
  
  
    // This function returns true if n can be
    // expressed sum of consecutive.
    function canBeSumofConsec(n)
    {
        // We basically return true if n is a
        // power of two
        return (((n&(n-1))!=0) && n!=0);
    }
        
        
// function call
      
    let n = 15;
    document.write(canBeSumofConsec(n) ? "true" : "false");
      
</script>

Producción: 

True

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Otro enfoque :

Sea el número elegido para representar N como suma de números consecutivos X + 1, X + 2, X + 3…. Y 

Suma de estos números elegidos = Suma de los primeros Y números naturales – Suma de los primeros X números naturales 

Suma del primer Y número natural =
Suma del primer X número natural =
Sabemos que,
N = Suma del primer Y número natural – Suma del primer X número natural




Sea Y – X = a, Y + X + 1 = b
Y + X + 1 > Y – X, b > a
,
2N = a * b
Significa que a y b son factores de 2N , sabemos que X e Y son enteros entonces,
1. b – a – 1 => múltiplo de 2 ( número par)
2. b + a + 1 => múltiplo de 2 (número par)

Ambas condiciones deben cumplirse

De 1 y 2 podemos decir que cualquiera de ellos (a, b) debe ser Impar y otro Par

Entonces, si el número (2N) tiene solo factores impares (no puede ser posible ya que es un número par (2N no N)) o solo factores pares, no podemos representarlo como una suma de números naturales consecutivos.

Entonces ahora, solo tenemos que verificar si tiene un factor impar o no.

1. Si el número (2N no N) no tiene ningún factor impar (contiene solo un factor par, lo que significa que se puede representar como ), entonces no podemos representarlo como una suma de números consecutivos.

2. Si el número (2N no N) tiene un factor impar entonces podemos representarlo como la suma de un número consecutivo

Después de esto, solo tenemos que verificar si podemos representar (2N como ) o no

• en caso afirmativo , la respuesta es falsa o 0
• si no , entonces la respuesta es verdadera o 1

A continuación se muestra la implementación de la idea anterior: 

#include <bits/stdc++.h>
using namespace std;
  
long long int canBeSumofConsec(long long int n) 
{ 
    // Updating n with 2n
    n = 2 * n;
    // (n & (n - 1)) => Checking whether we can write 2n as 2^k
    // if yes (can't represent 2n as 2^k) then answer 1
    // if no (can represent 2n as 2^k) then answer 0
    return ((n & (n - 1)) != 0);
}
  
int main()
{
    long long int n = 10;
    cout<<canBeSumofConsec(n)<<"\n";
}

#include <stdio.h>
  
long long int canBeSumofConsec(long long int n) 
{ 
    // Updating n with 2n
    n = 2 * n;
    // (n & (n - 1)) => Checking whether we can write 2n as 2^k
    // if yes (can't represent 2n as 2^k) then answer 1
    // if no (can represent 2n as 2^k) then answer 0
    return ((n & (n - 1)) != 0);
}
  
int main()
{
    long long int n = 10;
    printf("%lld", canBeSumofConsec(n));
}

import java.util.*;
class GFG{
  
 static int canBeSumofConsec( int n) 
{ 
    // Updating n with 2n
    n = 2 * n;
     
    // (n & (n - 1)) => Checking whether we can write 2n as 2^k
    // if yes (can't represent 2n as 2^k) then answer 1
    // if no (can represent 2n as 2^k) then answer 0
    return ((n & (n - 1)) != 0)?1:0;
}
  
public static void main(String[] args)
{
    int n = 10;
    System.out.print(canBeSumofConsec(n)+"\n");
}
}
  
// This code is contributed by umadevi9616 

def canBeSumofConsec(n):
    
    # Updating n with 2n
    n = 2 * n;
  
    # (n & (n - 1)) => Checking whether we can write 2n as 2^k
    # if yes (can't represent 2n as 2^k) then answer 1
    # if no (can represent 2n as 2^k) then answer 0
    if((n & (n - 1)) != 0):
        return 1;
    else:
        return 0;
  
if __name__ == '__main__':
    n = 10;
    print(canBeSumofConsec(n));
  
# This code is contributed by umadevi9616 

using System;
  
public class GFG {
  
    static int canBeSumofConsec(int n)
    {
        
        // Updating n with 2n
        n = 2 * n;
  
        // (n & (n - 1)) => Checking whether we can write 2n as 2^k
        // if yes (can't represent 2n as 2^k) then answer 1
        // if no (can represent 2n as 2^k) then answer 0
        return ((n & (n - 1)) != 0) ? 1 : 0;
    }
  
    public static void Main(String[] args) {
        int n = 10;
        Console.Write(canBeSumofConsec(n) + "\n");
    }
}
  
// This code is contributed by umadevi9616

<script>
  
    function canBeSumofConsec(n) {
        // Updating n with 2n
        n = 2 * n;
  
        // (n & (n - 1)) => Checking whether we can write 2n as 2^k
        // if yes (can't represent 2n as 2^k) then answer 1
        // if no (can represent 2n as 2^k) then answer 0
        return ((n & (n - 1)) != 0) ? 1 : 0;
    }
  
        var n = 10;
        document.write(canBeSumofConsec(n) + "\n");
  
// This code is contributed by umadevi9616
</script>

1

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Referencia:  
http://www.cut-the-knot.org/arithmetic/UnpropertyOfPowersOf2.shtml
Este artículo es una contribución de Sahil Chhabra . 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.