Given a positive integer N, find out how many positive integers strictly less than N have the same number of set bits as N.
Examples:
Input : 8 Output :3 Explanation: Binary representation of 8 : 1000, so number of set bits in 8 is 1. So the integers less than 8 with same number of set bits are : 4, 2, 1 Input :1 Output :0 Input :4 Output :2
Approach1:
1. Using __builtin_popcount() inbuilt function, count set bits in N and store into a temp variable 2. Iterate from n-1 to 1 and also count set bits in i using __builtin_popcount() function 3. Now, compare temp with __builtin_popcount(i) 4. If both are equal then increment counter variable 5. Return counter
Below is the implementation of the above approach.
C++
// CPP program to find numbers less than N// that have same Number Of Set Bits As N#include <iostream>using namespace std;int smallerNumsWithSameSetBits(int n){ // __builtin_popcount function that count // set bits in n int temp = __builtin_popcount(n); // Iterate from n-1 to 1 int count = 0; for (int i = n - 1; i > 0; i--) { // check if the number of set bits // equals to temp increment count if (temp == __builtin_popcount(i)) count++; } return count;}// Driver Code int main(){ int n = 4; cout << smallerNumsWithSameSetBits(n); return 0;} |
Java
// Java program to find numbers less than N// that have same Number Of Set Bits As Nclass GFG { // returns number of set bits in a number static int __builtin_popcount(int n) { int d, t = 0; while(n > 0) { d = n % 2; n = n / 2; if(d == 1) t++; } return t; } static int smallerNumsWithSameSetBits(int n) { // __builtin_popcount function that count // set bits in n int temp = __builtin_popcount(n); // Iterate from n-1 to 1 int count = 0; for (int i = n - 1; i > 0; i--) { // check if the number of set bits // equals to temp increment count if (temp == __builtin_popcount(i)) count++; } return count; } // Driver Code public static void main(String[] args) { int n = 4; System.out.println( smallerNumsWithSameSetBits(n)); }}// This code is contributed by Arnab Kundu. |
Python3
# Python3 program to find numbers # less than N that have same# Number Of Set Bits As Ndef __builtin_popcount(n) : t = 0 while(n > 0) : d = n % 2 n = int(n / 2) if(d == 1) : t = t + 1 return tdef smallerNumsWithSameSetBits(n) : # __builtin_popcount function # that count set bits in n temp = __builtin_popcount(n) # Iterate from n-1 to 1 count = 0 for i in range(n-1,0,-1) : # check if the number of # set bits equals to temp # increment count if (temp == __builtin_popcount(i)) : count = count + 1 return count# Driver Code n = 4print (smallerNumsWithSameSetBits(n))# This code is contributed by # Manish Shaw(manishshaw1) |
C#
// C# program to find numbers less than N// that have same Number Of Set Bits As Nusing System;class GFG { // returns number of set bits in a number static int __builtin_popcount(int n) { int d, t = 0; while(n > 0) { d = n % 2; n = n / 2; if(d == 1) t++; } return t; } static int smallerNumsWithSameSetBits(int n) { // __builtin_popcount function that count // set bits in n int temp = __builtin_popcount(n); // Iterate from n-1 to 1 int count = 0; for (int i = n - 1; i > 0; i--) { // check if the number of set bits // equals to temp increment count if (temp == __builtin_popcount(i)) count++; } return count; } // Driver Code static public void Main(String []args) { int n = 4; Console.WriteLine( smallerNumsWithSameSetBits(n)); }}// This code is contributed by Arnab Kundu. |
PHP
<?php// PHP program to find numbers // less than N that have same// Number Of Set Bits As Nfunction __builtin_popcount($n){ $t = 0; while($n > 0) { $d = $n % 2; $n = intval($n / 2); if($d == 1) $t++; } return $t;}function smallerNumsWithSameSetBits($n){ // __builtin_popcount function // that count set bits in n $temp = __builtin_popcount($n); // Iterate from n-1 to 1 $count = 0; for ($i = $n - 1; $i > 0; $i--) { // check if the number of // set bits equals to temp // increment count if ($temp == __builtin_popcount($i)) $count++; } return $count;}// Driver Code $n = 4;echo (smallerNumsWithSameSetBits($n));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// Javascript program to find numbers less than N// that have same Number Of Set Bits As N// returns number of set bits in a numberfunction __builtin_popcount(n){ var d, t = 0; while(n > 0) { d = n % 2; n = parseInt(n / 2); if(d == 1) t++; } return t;}function smallerNumsWithSameSetBits(n){ // __builtin_popcount function that count // set bits in n var temp = __builtin_popcount(n); // Iterate from n-1 to 1 var count = 0; for (var i = n - 1; i > 0; i--) { // check if the number of set bits // equals to temp increment count if (temp == __builtin_popcount(i)) count++; } return count;}// Driver Code var n = 4;document.write( smallerNumsWithSameSetBits(n));</script> |
Output:
2
Time Complexity: O(N log N), where N is the input number
Space Complexity: O(1)
Approach 2: This problem can be solved using Bit Manipulation and Pascal Triangle.
- First precompute all the required nCr where n is the log(N) or length of binary representation of N.
- Now start iterating from right side of binary representaion of N.
- when the bit is set then calculate numbers less than it by calculating number of ways to arrange set bits till this place in the length of binary representation so far that is equal to nCr.
- Keep adding this for every set bit encountered.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;long long dp[41][41];int pre = 0;long long ncr(int n, int r){ if (!pre) { // Using Pascal's triangle to precompute all // possible nCr pre = 1; dp[0][0] = 0; dp[1][0] = 1; dp[1][1] = 1; for (int i = 2; i <= 40; i++) { dp[i][0] = 1; for (int j = 1; j < i; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; } dp[i][i] = 1; } } return dp[n][r];}long long count(long long x){ long long ans = 0; long long cnt = 0; long long len = 0; while (x > 0) { if (x & 1) { cnt++; ans += ncr(len, cnt); } len++; x >>= 1; } return ans;}int main(){ int N = 4; cout << count(N) << endl; return 0;} |
Java
public class Main { static long[][] dp = new long[41][41]; static int pre = 0; static long ncr(long n, long r) { if (pre == 0) { // Using Pascal's triangle to precompute all // possible nCr pre = 1; dp[0][0] = 0; dp[1][0] = 1; dp[1][1] = 1; for (int i = 2; i <= 40; i++) { dp[i][0] = 1; for (int j = 1; j < i; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; } dp[i][i] = 1; } } return dp[(int)n][(int)r]; } static long count(long x) { long ans = 0; long cnt = 0; long len = 0; while (x > 0) { if ((x & 1) == 1) { cnt++; ans += ncr(len, cnt); } len++; x >>= 1; } return ans; } public static void main(String[] args) { int N = 4; System.out.println(count(N)); }}// This code is contributed by ishankhandelwals. |
Python3
dp = [[0 for i in range(41)] for j in range(41)]pre = 0def ncr(n, r): global pre if pre == 0: pre = 1 dp[0][0] = 0 dp[1][0] = 1 dp[1][1] = 1 for i in range(2, 41): dp[i][0] = 1 for j in range(1, i): dp[i][j] = dp[i-1][j] + dp[i-1][j-1] dp[i][i] = 1 return dp[n][r]def count(x): ans = 0 cnt = 0 len = 0 while x > 0: if x & 1: cnt += 1 ans += ncr(len, cnt) len += 1 x >>= 1 return ansN = 4print(count(N))# This code is contributed by ishankhandelwals. |
C#
using System;class GFG { static int ncr(int n, int r) { int[, ] dp = new int[41, 41]; int pre = 0; if (pre == 0) { // Using Pascal's triangle to precompute all // possible nCr pre = 1; dp[0, 0] = 0; dp[1, 0] = 1; dp[1, 1] = 1; for (int i = 2; i <= 40; i++) { dp[i, 0] = 1; for (int j = 1; j < i; j++) { dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1]; } dp[i, i] = 1; } } return dp[n, r]; } static int count(int x) { int ans = 0; int cnt = 0; int len = 0; while (x > 0) { if ((x & 1) != 0) { cnt++; ans += ncr(len, cnt); } len++; x >>= 1; } return ans; } static void Main() { int N = 4; Console.Write(count(N)); }}// This code is contributed by garg28harsh. |
Javascript
let dp= new Array(41);let pre = 0;function ncr(n, r){ if (pre == 0) { // Using Pascal's triangle to precompute all // possible nCr pre = 1; dp[0][0] = 0; dp[1][0] = 1; dp[1][1] = 1; for (let i = 2; i <= 40; i++) { dp[i][0] = 1; for (let j = 1; j < i; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]; } dp[i][i] = 1; } } return dp[n][r];}function count( x){ let ans = 0; let cnt = 0; let len = 0; for(let i=0;i<41;i++) dp[i] = new Array(41); while (x > 0) { if (x & 1) { cnt++; ans += ncr(len, cnt); } len++; x >>= 1; } return ans;} let N = 4; console.log(count(N)); // This code is contributed by garg28harsh. |
Output
2
Time Complexity: O(log N)
Space Complexity: O(N^2).
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!
