Count of binary strings of given length consisting of at least one 1
Given an integer N, the task is to print the number of binary strings of length N which at least one ‘1’.
Examples:
Input: 2
Output: 3
Explanation:
“01”, “10” and “11” are the possible stringsInput: 3
Output: 7
Explanation:
“001”, “011”, “010”, “100”, “101”, “110” and “111” are the possible strings
Approach:
We can observe that:
Only one string of length N does not contain any 1, the one filled with only 0’s.
Since 2N strings are possible of length N, the required answer is 2N – 1.
Follow the steps below to solve the problem:
- Initialize X = 1.
- Compute upto 2N by performing bitwise left shift on X, N-1 times.
- Finally, print X – 1 as the required answer.
Below is the implementation of our approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to return // the count of strings long count_strings( long n) { int x = 1; // Calculate pow(2, n) for ( int i = 1; i < n; i++) { x = (1 << x); } // Return pow(2, n) - 1 return x - 1; } // Driver Code int main() { long n = 3; cout << count_strings(n); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to return // the count of Strings static long count_Strings( long n) { int x = 1 ; // Calculate Math.pow(2, n) for ( int i = 1 ; i < n; i++) { x = ( 1 << x); } // Return Math.pow(2, n) - 1 return x - 1 ; } // Driver Code public static void main(String[] args) { long n = 3 ; System.out.print(count_Strings(n)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement # the above approach # Function to return # the count of Strings def count_Strings(n): x = 1 ; # Calculate pow(2, n) for i in range ( 1 , n): x = ( 1 << x); # Return pow(2, n) - 1 return x - 1 ; # Driver Code if __name__ = = '__main__' : n = 3 ; print (count_Strings(n)); # This code is contributed by Princi Singh |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to return // the count of Strings static long count_Strings( long n) { int x = 1; // Calculate Math.Pow(2, n) for ( int i = 1; i < n; i++) { x = (1 << x); } // Return Math.Pow(2, n) - 1 return x - 1; } // Driver Code public static void Main(String[] args) { long n = 3; Console.Write(count_Strings(n)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program to implement // the above approach // Function to return // the count of Strings function count_Strings(n) { var x = 1; // Calculate Math.pow(2, n) for (i = 1; i < n; i++) { x = (1 << x); } // Return Math.pow(2, n) - 1 return x - 1; } // Driver Code var n = 3; document.write(count_Strings(n)); // This code is contributed by todaysgaurav </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)