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