Given a number n. Find the sum of all numbers up to n whose 2 bits are set.
Examples:
Input : 10 Output : 33 3 + 5 + 6 + 9 + 10 = 33 Input : 100 Output : 762
Naive Approach: Find each number up to n whose 2 bits are set. If its 2 bits are set add it to the sum.
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 bitsint countSetBits(int n){ int count = 0; while (n) { n &= (n - 1); count++; } return count;}// To calculate sum of numbersint 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 functionint main(){ int n = 10; cout << findSum(n); return 0;} |
Java
// Java program to find sum of numbers// upto n whose 2 bits are setpublic 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 bitsdef countSetBits(n): count = 0 while (n): n =n & (n - 1) count=count + 1 return count# To calculate sum of numbersdef 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 coden = 10print(findSum(n))# This code is contributed# by Anant Agarwal. |
C#
// C# program to find sum of // numbers upto n whose 2 // bits are setusing 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 bitsfunction countSetBits($n){ $count = 0; while ($n) { $n &= ($n - 1); $count++; } return $count;}// To calculate sum of numbersfunction 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 bitsfunction countSetBits(n){ let count = 0; while (n) { n &= (n - 1); count++; } return count;}// To calculate sum of numbersfunction 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> |
Output:
33
Time Complexity : O(n)
Space Complexity : O(1)
Efficient Approach: The number whose 2 bits are set is of the form 2^x + 2^y and this number is less than n. So we have to find only numbers in the range up to n which is of form 2^i + 2^j where i > 0 and 2^i < n and 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 numbersint 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 than 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 setpublic 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 than 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 than n # we don't include this in sum if (num <= n) : sum += num i += 1 # Return sum of numbers return sum# Driver Coden = 10print(findSum(n))# This code is contributed # by Smitha |
C#
// C# program to find sum of numbers// upto n whose 2 bits are setusing 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 than 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 numbersfunction 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 than 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 than 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> |
Output :
33
Time Complexity : O((log n)*(log n))
Space Complexity : O(1)
This article is contributed by nuclode. If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
