A Digit in the Concatenated Fibonacci Sequence
National Olympiad — Regional round (2010 season)
Submission name: fib.cpp
Problem summary
Concatenate Fibonacci numbers1,1,2,3,5,… without separators. Find the digit at1-based position n.
Input
One integer n.
Output
The digit at that position.
Constraints
1 ≤ n ≤500.
Worked example
Input and output for the worked example discussed below.
Input
12
Output
4
Solution analysis
- Start the digit string with11, representing the two initial Fibonacci ones. Keep the last two numeric Fibonacci values so the next is their sum.
- Append each next number’s decimal representation until the accumulated string reaches position n. Under n≤500, fewer than71 terms suffice and the generated Fibonacci numbers fit signed64-bit.
- The beginning11235813213455 has its twelfth digit4. After building enough digits, use string index n−1 because C++ strings are0-based while the requested position is1-based.
Why it works
Induction on generated terms shows the string is exactly the prescribed Fibonacci concatenation. The loop stops only after the target position exists, so indexing n−1 returns precisely its requested digit.
Complexity: O(n) time and O(n) space under the given bounded domain; total appended digits are only slightly more than n.
Watch out. Include both initial ones, convert the1-based requested position correctly, and do not assume all Fibonacci terms have one digit.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int position;
cin>>position;
long long previous=1;
long long current=1;
string digits="11";
while(int(digits.size())<position){
long long next=previous+current;
previous=current;
current=next;
// Append whole Fibonacci numbers without separators.
digits+=to_string(current);
}
cout<<digits[position-1]<<'\n';
}