Dado un número n. Encuentre la suma de todos los números hasta n cuyos 2 bits están establecidos.
Ejemplos:
Input : 10 Output : 33 3 + 5 + 6 + 9 + 10 = 33 Input : 100 Output : 762
Enfoque ingenuo: encuentre cada número hasta n cuyos 2 bits estén establecidos. Si sus 2 bits están establecidos, agréguelos a la suma.
C++
// CPP program to find sum of numbers
// upto n whose 2 bits are set
#include <bits/stdc++.h>
using namespace std;
// To count number of set bits
int countSetBits(int n)
{
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
// To calculate sum of numbers
int findSum(int n)
{
int sum = 0;
// To count sum of number
// whose 2 bit are set
for (int i = 1; i <= n; i++)
if (countSetBits(i) == 2)
sum += i;
return sum;
}
// Driver program to test above function
int main()
{
int n = 10;
cout << findSum(n);
return 0;
}
Java
// Java program to find sum of numbers
// upto n whose 2 bits are set
public class Main {
// To count number of set bits
static int countSetBits(int n)
{
int count = 0;
while (n > 0) {
n &= (n - 1);
count++;
}
return count;
}
// To calculate sum of numbers
static int findSum(int n)
{
int sum = 0;
// To count sum of number
// whose 2 bit are set
for (int i = 1; i <= n; i++)
if (countSetBits(i) == 2)
sum += i;
return sum;
}
// Driver program to test above function
public static void main(String[] args)
{
int n = 10;
System.out.println(findSum(n));
}
}
Python3
# Python program to find # sum of numbers # upto n whose 2 bits are set # To count number of set bits def countSetBits(n): count = 0 while (n): n =n & (n - 1) count=count + 1 return count # To calculate sum of numbers def findSum(n): sum = 0 # To count sum of number # whose 2 bit are set for i in range(1,n+1): if (countSetBits(i) == 2): sum =sum + i return sum # Driver code n = 10 print(findSum(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find sum of
// numbers upto n whose 2
// bits are set
using System;
class GFG
{
// To count number
// of set bits
static int countSetBits(int n)
{
int count = 0;
while (n > 0)
{
n = n & (n - 1);
count++;
}
return count;
}
// To calculate
// sum of numbers
static int findSum(int n)
{
int sum = 0;
// To count sum of number
// whose 2 bit are set
for (int i = 1; i <= n; i++)
if (countSetBits(i) == 2)
sum += i;
return sum;
}
// Driver Code
static public void Main ()
{
int n = 10;
Console.WriteLine(findSum(n));
}
}
// This code is contributed by aj_36
PHP
<?php
// PHP program to find sum of numbers
// upto n whose 2 bits are set
// To count number of set bits
function countSetBits($n)
{
$count = 0;
while ($n)
{
$n &= ($n - 1);
$count++;
}
return $count;
}
// To calculate sum of numbers
function findSum($n)
{
$sum = 0;
// To count sum of number
// whose 2 bit are set
for ($i = 1; $i <= $n; $i++)
if (countSetBits($i) == 2)
$sum += $i;
return $sum;
}
// Driver Code
$n = 10;
echo findSum($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find sum of numbers
// upto n whose 2 bits are set
// To count number of set bits
function countSetBits(n)
{
let count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
// To calculate sum of numbers
function findSum(n)
{
let sum = 0;
// To count sum of number
// whose 2 bit are set
for (let i = 1; i <= n; i++)
if (countSetBits(i) == 2)
sum += i;
return sum;
}
// Driver program to test above function
let n = 10;
document.write(findSum(n));
// This code is contributed by Mayank Tyagi
</script>
Producción:
33
Complejidad de tiempo : O(n)
Complejidad espacial : O(1)
Enfoque eficiente: el número cuyos 2 bits están configurados tiene la forma 2^x + 2^y y este número es menor que n. Así que tenemos que encontrar solo números en el rango hasta n que es de la forma 2^i + 2^j donde i > 0 y 2^i < n y 0 <= j < i.
C++
// C++ program to find sum of numbers
// upto n whose 2 bits are set
#include <bits/stdc++.h>
using namespace std;
// To calculate sum of numbers
int findSum(int n)
{
int sum = 0;
// Find numbers whose 2 bits are set
for (int i = 1; (1 << i) < n; i++) {
for (int j = 0; j < i; j++) {
int num = (1 << i) + (1 << j);
// If number is greater then n
// we don't include this in sum
if (num <= n)
sum += num;
}
}
// Return sum of numbers
return sum;
}
// Driver program to test findSum()
int main()
{
int n = 10;
cout << findSum(n);
return 0;
}
Java
// Java program to find sum of numbers
// upto n whose 2 bits are set
public class Main {
// To calculate sum of numbers
static int findSum(int n)
{
int sum = 0;
// Find numbers whose 2 bits are set
for (int i = 1; 1 << i < n; i++) {
for (int j = 0; j < i; j++) {
int num = (1 << i) + (1 << j);
// If number is greater then n
// we don't include this in sum
if (num <= n)
sum += num;
}
}
// Return sum of numbers
return sum;
}
// Driver program to test findSum()
public static void main(String[] args)
{
int n = 10;
System.out.println(findSum(n));
}
}
Python3
# Python3 program to find sum of # numbers upto n whose 2 bits are set # To calculate sum of numbers def findSum(n) : sum = 0 # Find numbers whose 2 # bits are set i = 1 while((1 << i) < n ) : for j in range(0, i) : num = (1 << i) + (1 << j) # If number is greater then n # we don't include this in sum if (num <= n) : sum += num i += 1 # Return sum of numbers return sum # Driver Code n = 10 print(findSum(n)) # This code is contributed # by Smitha
C#
// C# program to find sum of numbers
// upto n whose 2 bits are set
using System;
public class main {
// To calculate sum of numbers
static int findSum(int n)
{
int sum = 0;
// Find numbers whose 2 bits are set
for (int i = 1; 1 << i < n; i++)
{
for (int j = 0; j < i; j++)
{
int num = (1 << i) + (1 << j);
// If number is greater then n
// we don't include this in sum
if (num <= n)
sum += num;
}
}
// Return sum of numbers
return sum;
}
// Driver Code
public static void Main(String []args)
{
int n = 10;
Console.WriteLine(findSum(n));
}
}
// This Code is contributed by vt_m.
PHP
<?php
<?php
// PHP program to find sum of numbers
// upto n whose 2 bits are set
// To calculate sum of numbers
function findSum($n)
{
$sum = 0;
// Find numbers whose 2 bits are set
for ($i = 1; (1 << $i) < $n; $i++)
{
for ($j = 0; $j < $i; $j++)
{
$num = (1 << $i) + (1 << $j);
// If number is greater then n
// we don't include this in sum
if ($num <= $n)
$sum += $num;
}
}
// Return sum of numbers
return $sum;
}
// Driver Code
$n = 10;
echo findSum($n);
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript program to find sum of numbers
// upto n whose 2 bits are set
// To calculate sum of numbers
function findSum(n)
{
let sum = 0;
// Find numbers whose 2 bits are set
for (let i = 1; 1 << i < n; i++)
{
for (let j = 0; j < i; j++)
{
let num = (1 << i) + (1 << j);
// If number is greater then n
// we don't include this in sum
if (num <= n)
sum += num;
}
}
// Return sum of numbers
return sum;
}
let n = 10;
document.write(findSum(n));
</script>
Producción :
33
Complejidad del tiempo: O((log n)*(log n))
Complejidad espacial: O(1)
Este artículo es una contribución de nuclode . 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.
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