Bit Strings Solution

10 September 2021

Statement

( The original statement can be found here )
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.

Input
The only input line has an integer n.

Output
Print the result modulo \(10^9 +7\).

Constraints
1 ≤ n ≤ \(10^6\)
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
3

Output :
8

Solution

A bit string is a sequence consisting of 0's and 1's. If the length of this sequence is \(N\), how many distinct bit strings can we make ? As you may have guessed, this is a combinatorics problem.

If \(f(n)\) is the function that gives us the number of combinations then we can say the following :
$$f(n) = 2 \times f(n-1)$$ This means that the number of possible bit strings doubles every time we add a new bit to the sequence. This makes sense if we think about it, because by adding one bit, we will have all previous combinations with the \(Nth\) bit assigned to \(1\) plus all the previous combinations with the \(Nth\) bit assigned to 0, hence doubling it.

But how can we compute this result modulo \(10^9+7\) ? We can use our trusty modular property to deal with this : $$2^2 \: mod \: c = (2\:mod\:c\:\times2\:mod\:c)\:mod\:c$$ $$2^3 \: mod \: c = (2^2\:mod\:c\:\times2\:mod\:c)\:mod\:c$$ $$2^4 \: mod \: c = (2^3\:mod\:c\:\times2\:mod\:c)\:mod\:c$$ $$.$$ $$.$$ $$.$$

With this property we can simply double our answer \(N\) times and use the modulo on each iteration without ruining our final result.

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

int main() {
    int n, answer = 1;
    cin >> n;
    for (int i = 0; i < n; i++) {
        answer *= 2;
        answer %= MOD;
    }
    cout << answer;
}

This solution runs in time complexity of \(O(N)\) and space complexity of \(O(1)\).