Contar números hasta N que no se pueden expresar como la suma de al menos dos enteros positivos consecutivos

Dado un número entero positivo N , la tarea es encontrar el número de números enteros del rango [1, N] tal que el número entero no se pueda expresar como la suma de dos o más números enteros positivos consecutivos .

Ejemplos:

Entrada: N = 10
Salida: 4
Explicación: Los enteros que no se pueden expresar como la suma de dos o más enteros consecutivos son {1, 2, 4, 8}. Por lo tanto, la cuenta de números enteros es 4.

Entrada: N = 100
Salida: 7

Enfoque ingenuo: el problema dado se puede resolver basándose en la observación de que si un número es una potencia de dos , entonces no se puede expresar como una suma de números consecutivos. Siga los pasos a continuación para resolver el problema dado:

  • Inicialice una variable, digamos count , que almacena el recuento de números en el rango [1, N] que no se puede expresar como una suma de dos o más números enteros consecutivos.
  • Itere sobre el rango [1, N] , y si el número i es una potencia perfecta de 2 , entonces incremente el valor de count en 1 .
  • Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a number can
// be expressed as a power of 2
bool isPowerof2(unsigned int n)
{
    // f N is power of
    // two
    return ((n & (n - 1)) && n);
}
 
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
void countNum(int N)
{
    // Stores the resultant
    // count of integers
    int count = 0;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Check if i is power of 2
        bool flag = isPowerof2(i);
 
        // Increment the count if i
        // is not power of 2
        if (!flag) {
            count++;
        }
    }
 
    // Print the value of count
    cout << count << "\n";
}
 
// Driver Code
int main()
{
    int N = 100;
    countNum(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if a number can
// be expressed as a power of 2
static boolean isPowerof2(int n)
{
     
    // f N is power of
    // two
    return ((n & (n - 1)) > 0 && n > 0);
}
 
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
static void countNum(int N)
{
     
    // Stores the resultant
    // count of integers
    int count = 0;
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Check if i is power of 2
        boolean flag = isPowerof2(i);
 
        // Increment the count if i
        // is not power of 2
        if (!flag)
        {
            count++;
        }
    }
 
    // Print the value of count
    System.out.print(count + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 100;
     
    countNum(N);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach
 
# Function to check if a number can
# be expressed as a power of 2
def isPowerof2(n):
    # if N is power of
    # two
    return ((n & (n - 1)) and n)
 
# Function to count numbers that
# cannot be expressed as sum of
# two or more consecutive +ve integers
def countNum(N):
    # Stores the resultant
    # count of integers
    count = 0
 
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
       
        # Check if i is power of 2
        flag = isPowerof2(i)
 
        # Increment the count if i
        # is not power of 2
        if (not flag):
            count += 1
 
    # Print the value of count
    print(count)
 
# Driver Code
if __name__ == '__main__':
 
    N = 100
    countNum(N)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if a number can
// be expressed as a power of 2
static bool isPowerof2(int n)
{
     
    // f N is power of
    // two
    return ((n & (n - 1)) > 0 && n > 0);
}
 
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
static void countNum(int N)
{
     
    // Stores the resultant
    // count of integers
    int count = 0;
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Check if i is power of 2
        bool flag = isPowerof2(i);
 
        // Increment the count if i
        // is not power of 2
        if (!flag)
        {
            count++;
        }
    }
 
    // Print the value of count
    Console.Write(count + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 100;
     
    countNum(N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to check if a number can
// be expressed as a power of 2
function isPowerof2(n)
{
    // f N is power of
    // two
    return ((n & (n - 1)) && n);
}
  
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
function countNum(N)
{
    // Stores the resultant
    // count of integers
    let count = 0;
  
    // Iterate over the range [1, N]
    for (let i = 1; i <= N; i++) {
  
        // Check if i is power of 2
        let flag = isPowerof2(i);
  
        // Increment the count if i
        // is not power of 2
        if (!flag) {
            count++;
        }
    }
  
    // Print the value of count
    document.write(count + "\n");
}
      
// Driver code
 
    let N = 100;
    countNum(N);
 
// This code is contributed by souravghosh0416.
</script>
Producción: 

7

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar basándose en la observación de que los números enteros que no son potencias de 2 , excepto 2 , se pueden expresar como la suma de dos o más números enteros positivos consecutivos. Por lo tanto, la cuenta de dichos enteros en el rango [1, N] está dada por (log 2 N + 1).

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
void countNum(int N)
{
    // Stores the count
// of such numbers
    int ans = log2(N) + 1;
 
    cout << ans << "\n";
}
 
// Driver Code
int main()
{
    int N = 100;
    countNum(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to count numbers that
    // cannot be expressed as sum of
    // two or more consecutive +ve integers
    static void countNum(int N)
    {
       
        // Stores the count
        // of such numbers
        int ans = (int)(Math.log(N) / Math.log(2)) + 1;
 
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 100;
        countNum(N);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python 3 program for the above approach
import math
 
# Function to count numbers that
# cannot be expressed as sum of
# two or more consecutive +ve integers
def countNum(N):
 
    # Stores the count
        # of such numbers
    ans = int(math.log2(N)) + 1
 
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    N = 100
    countNum(N)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
static void countNum(int N)
{
     
    // Stores the count
    // of such numbers
    int ans = (int)(Math.Log(N) /
                    Math.Log(2)) + 1;
 
   Console.WriteLine(ans);
}
 
// Driver Code
static void Main()
{
    int N = 100;
    countNum(N);
}
}
 
// This code is contributed by SoumikMondal.

Javascript

<script>
 
// Javascript program for the above approach
 
 
// Function to count numbers that
// cannot be expressed as sum of
// two or more consecutive +ve integers
function countNum(N)
{
   
    // Stores the count
    // of such numbers
    var ans = parseInt(Math.log(N) / Math.log(2)) + 1;
 
    document.write(ans);
}
 
// Driver Code
var N = 100;
countNum(N);
 
// This code contributed by shikhasingrajput
 
</script>
Producción: 

7

 

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por koulick_sadhu 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 *