bit-strings

Bit Strings

CSES easy

Your task is to calculate the number of bit strings of length \(n\).

A bit string is a sequence of \(n\) characters, each of which is either 0 or 1.

For example, if \(n = 3\), the bit strings are [000, 001, 010, 011, 100, 101, 110, 111], so there are \(8\) such strings.

Input:

A single integer \(n\).

Output:

Print the total number of bit strings of length \(n\), modulo \(10^9 + 7\).

Constraints:

\(1 \le n \le 10^6\)

Example:

Input:

Output:

Solution

Each of the \(n\) positions in the bit string has 2 independent choices: 0 or 1. So, by the rule of product, the number of bit strings is \(2^n\). We must print this value modulo \(M = 10^9 + 7\).

We can compute \(2^n \bmod M\) sequentially with a simple loop:

Start with ans = 1.
Repeat n times:

\(\text{ans} = (2 \cdot \text{ans}) \bmod M.\)

After \(n\) iterations, ans equals \(2^n \bmod M\).

This runs in \(O(n)\) time. Since \(n \le 10^6\), a loop with \(10^6\) iterations is easily within the time limit.

Sequential idea:

Initialize ans = 1
for i = 1 to n:
    ans = (ans * 2) % M
    output ans

#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    long long ans = 1;
    for (long long i = 0; i < n; ++i) {
        ans = (ans * 2) % MOD;
    }

    cout << ans << "\n";
    return 0;
}

Note on modular exponentiation (alternative)

For this problem, an \(O(n)\) loop is fast enough. In problems where \(n\) can be much larger (e.g., up to \(10^{18}\)), we cannot loop \(n\) times.

In those cases, we should use binary (fast) modular exponentiation to compute \(2^n \bmod M\) in \(O(\log n)\) time instead of \(O(n)\).