DSA sheet / Introductory
Bit Strings
The problem in brief
Given n up to a million, print how many different strings of n bits (zeros and ones) exist, taken modulo 10^9 + 7.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1617.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Count the choices per position. How many independent choices are there, and how many options does each one have?
-
The answer is a power of two, and it is astronomically large for big n. What does the “modulo” in the statement let you do while you compute?
-
You may reduce after every multiplication instead of once at the end, because (a * b) mod m equals ((a mod m) * (b mod m)) mod m. Which integer type holds the intermediate product?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
The counting principle is simple: independent choices multiply. Each of the n positions has two options, so the number of strings is 2 * 2 * … * 2 = 2^n. The interesting part is arithmetic, not combinatorics: 2^n has hundreds of thousands of digits, so you never build it. You keep a running remainder and multiply by 2 one step at a time, reducing as you go.
For n up to a million a simple loop is fast. In problems where the exponent is up to 10^18 the same idea needs fast exponentiation (square and multiply); it is worth knowing now because the next problem in your toolbox, “Exponentiation”, is exactly that. The habit is: state a big-number problem as a chain of small modular operations.
Intuition
Every extra bit doubles the number of strings: one bit gives 2, two bits give 4, three give 8. Writing the answer mod 10^9 + 7 is like keeping only the last “clock position” of a huge counter; doubling the clock position and wrapping around gives the same clock position as doubling the huge counter.
Approach
- Start with result = 1.
- Repeat n times: result = (result * 2) mod (10^9 + 7).
- Print result.
Pitfall: result stays below 10^9 + 7, so result * 2 stays just under a signed 32-bit int’s limit here, but the same loop with a multiplier of 3 or more would overflow. Make it a habit to keep modular products in 64-bit (long long, long) and reduce right after each multiplication.
Complexity
O(n) time with the loop (O(log n) with fast exponentiation), O(1) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
const long long MOD = 1000000007LL;
long long result = 1;
for (long long i = 0; i < n; i++) result = result * 2 % MOD;
cout << result << "\n";
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
MOD = 10**9 + 7
result = 1
for _ in range(n):
result = result * 2 % MOD
print(result)
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(in.readLine().trim());
final long MOD = 1_000_000_007L;
long result = 1;
for (long i = 0; i < n; i++) result = result * 2 % MOD;
System.out.println(result);
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
const MOD = 1000000007;
let result = 1;
for (let i = 0; i < n; i++) result = (result * 2) % MOD;
console.log(result);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).