Given two integers N and K, the task is to find the count of numbers up to N having K-th (0-based indexing) bit set.
Examples:
Input: N = 14, K = 2
Output: 7
Explanation:
The numbers less than equal to 14, having 2nd bit set are 4, 5, 6, 7, 12, 13, and 14.Input: N = 6, K = 1
Output: 3
Explanation:
The numbers less than equal to 6 having 1st bit set are 1, 3, 5.
Naive Approach: The simplest approach is to traverse from 1 to N, and check for each number whether its K-th bit is set or not.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by dividing the task into two parts:
- First, right shift N, K+1 times followed by left shifting the result K times, which gives the count of numbers satisfying the given condition till the nearest power of 2 less than N.
- Now, check if the Kth bit is set in N or not.
- If the Kth bit is set in N, then add the count of numbers from the nearest power of 2 less than N to the answer.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of number of 1's at ith bit// in a range [1, n - 1]long long getcount(long long n, int k){ // Store count till nearest // power of 2 less than N long long res = (n >> (k + 1)) << k; // If K-th bit is set in N if ((n >> k) & 1) // Add to result the nearest // power of 2 less than N res += n & ((1ll << k) - 1); // Return result return res;}// Driver Codeint main(){ long long int N = 14; int K = 2; // Function Call cout << getcount(N + 1, K) << endl; return 0;} |
Java
// Java program for above approachclass GFG{ // Function to return the count // of number of 1's at ith bit // in a range [1, n - 1] static long getcount(long n, int k) { // Store count till nearest // power of 2 less than N long res = (n >> (k + 1)) << k; // If K-th bit is set in N if (((n >> k) & 1) != 0) // Add to result the nearest // power of 2 less than N res += n & ((1 << k) - 1); // Return result return res; } // Driver code public static void main(String[] args) { long N = 14; int K = 2; // Function Call System.out.println(getcount(N + 1, K)); }}// This code is contributed by divyesh072019 |
Python3
# Python3 program for above approach# Function to return the count# of number of 1's at ith bit# in a range [1, n - 1]def getcount(n, k): # Store count till nearest # power of 2 less than N res = (n >> (k + 1)) << k # If K-th bit is set in N if ((n >> k) & 1): # Add to result the nearest # power of 2 less than N res += n & ((1 << k) - 1) # Return result return res# Driver Codeif __name__ == '__main__': N = 14 K = 2 # Function Call print (getcount(N + 1, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for above approachusing System;class GFG{// Function to return the count// of number of 1's at ith bit// in a range [1, n - 1]static long getcount(long n, int k){ // Store count till nearest // power of 2 less than N long res = (n >> (k + 1)) << k; // If K-th bit is set in N if (((n >> k) & 1) != 0) // Add to result the nearest // power of 2 less than N res += n & ((1 << k) - 1); // Return result return res;}// Driver Code static void Main() { long N = 14; int K = 2; // Function Call Console.WriteLine(getcount(N + 1, K));}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program for above approach // Function to return the count // of number of 1's at ith bit // in a range [1, n - 1] function getcount(n, k) { // Store count till nearest // power of 2 less than N let res = (n >> (k + 1)) << k; // If K-th bit is set in N if (((n >> k) & 1) != 0) // Add to result the nearest // power of 2 less than N res += n & ((1 << k) - 1); // Return result return res; } let N = 14; let K = 2; // Function Call document.write(getcount(N + 1, K)); </script> |
Output:
7
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
