Count of numbers whose 0th and Nth bits are set
Given a positive integer N, the task is to count the numbers that can be represented with N bits and whose 0th and Nth bits are set.
Examples:
Input: N = 2
Output: 1
All possible 2-bit integers are 00, 01, 10 and 11.
Out of which only 11 has 0th and Nth bit set.
Input: N = 4
Output: 4
Approach: Out of the given N bits, only two bits need to be set i.e. the 0th and the Nth bit. So, setting these 2 bits as 1 we are left with the rest N – 2 bits every single of which can either be 0 or 1 and there are 2N – 2 ways of doing that.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count of n-bit // numbers whose 0th and nth bits are set int countNum( int n) { if (n == 1) return 1; int count = pow (2, n - 2); return count; } // Driver code int main() { int n = 3; cout << countNum(n); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to return the count of n-bit // numbers whose 0th and nth bits are set static int countNum( int n) { if (n == 1 ) return 1 ; int count = ( int ) Math.pow( 2 , n - 2 ); return count; } // Driver code public static void main (String[] args) { int n = 3 ; System.out.println(countNum(n)); } } // This code is contributed by ajit |
Python
# Python3 implementation of the approach # Function to return the count of n-bit # numbers whose 0th and nth bits are set def countNum(n): if (n = = 1 ): return 1 count = pow ( 2 , n - 2 ) return count # Driver code n = 3 print (countNum(n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count of n-bit // numbers whose 0th and nth bits are set static int countNum( int n) { if (n == 1) return 1; int count = ( int ) Math.Pow(2, n - 2); return count; } // Driver code static public void Main () { int n = 3; Console.WriteLine(countNum(n)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the count of n-bit // numbers whose 0th and nth bits are set function countNum(n) { if (n == 1) return 1; let count = Math.pow(2, n - 2); return count; } // Driver code let n = 3; document.write(countNum(n)); </script> |
Output:
2
Time Complexity: O(logn)
Auxiliary Space: O(1)
Contact Us