CSES Solutions – Bit Strings
Your task is to calculate the number of bit strings of length N. For example, if N=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111. Print the result modulo 109+7.
Examples:
Input: N = 2
Output: 4
Explanation: There are total 4 bit strings possible of length 2: 00, 01, 10 and 11.Input: N = 10
Output: 1024
Explanation: There are total 1024 bit strings possible of length 10.
Approach: To solve the problem, follow the below idea:
We need to construct a string of length N where each character can either be a ‘0’ or a ‘1’. So, for every index we have 2 choices and in total we have N characters so the number of bit strings that can be formed using N bits will be 2 ^ N. So, we can find the answer by computing (2 ^ N) % (109+7). This can be calculated using Binary Exponentiation.
Step-by-step algorithm:
- Maintain a function, say power(base, expo) to calculate (base ^ power) % mod.
- Return power(2, N) as the final answer.
Below is the implementation of algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll MOD = 1e9 + 7;
// Fast Exponentiation
ll power(ll base, ll expo) {
ll ans = 1;
while(expo) {
if(expo & 1LL) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
expo >>= 1LL;
}
return ans;
}
int main() {
ll N = 5;
cout << power(2LL, N) << endl;
return 0;
}
public class FastExponentiation {
static long MOD = 1000000007;
// Fast Exponentiation
static long power(long base, long expo) {
long ans = 1;
while (expo > 0) {
if ((expo & 1) == 1) {
ans = (ans * base) % MOD;
}
base = (base * base) % MOD;
expo >>= 1;
}
return ans;
}
public static void main(String[] args) {
long N = 5;
System.out.println(power(2, N));
}
}
// This code is contributed by akshitaguprzj3
MOD = 10**9 + 7
# Fast Exponentiation
def power(base, expo):
ans = 1
while expo:
if expo & 1:
ans = (ans * base) % MOD
base = (base * base) % MOD
expo >>= 1
return ans
if __name__ == "__main__":
N = 5
print(power(2, N))
using System;
public class GFG
{
static long MOD = 1000000007;
// Fast Exponentiation
static long Power(long baseVal, long expo)
{
long ans = 1;
while (expo > 0)
{
if ((expo & 1) == 1)
{
ans = (ans * baseVal) % MOD;
}
baseVal = (baseVal * baseVal) % MOD;
expo >>= 1;
}
return ans;
}
public static void Main(string[] args)
{
long N = 5;
Console.WriteLine(Power(2, N));
}
}
// Define the modulo value
const MOD = 1e9 + 7;
// Function for fast exponentiation using binary exponentiation
function power(base, expo) {
let ans = 1; // Initialize result
// Iterate until expo becomes 0
while (expo) {
// If the least significant bit of expo is set
if (expo & 1) {
// Update ans by multiplying it with base and taking modulo
ans = (ans * base) % MOD;
}
// Update base by squaring it and taking modulo
base = (base * base) % MOD;
// Right shift expo by 1 to divide it by 2
expo >>= 1;
}
// Return the final result
return ans;
}
// Main function to demonstrate fast exponentiation
function main() {
let N = 5; // Exponent value
console.log(power(2, N)); // Calculate and output 2^N modulo MOD
}
// Call the main function
main();
Output
32
Time Complexity: O(logN), where N is the length of string we need to construct.
Auxiliary Space: O(1)
Contact Us