Digit of Concatenated Powers
Autumn Tournament (2014)
Submission name: seq.cpp
Problem summary
Write 1, x, x², x³, ... consecutively without spaces. Find the n-th decimal digit of the resulting infinite sequence, counting from 1.
Input
Two integers x and n.
Output
The digit in position n.
Constraints
1 < x < 1000; 1 < n < 1000000.
Worked example
Original statement sample.
Input
3 9
Output
4
Solution analysis
- The powers quickly exceed long long, so store the current power as decimal digits in reverse order. Initially it is the one-digit number 1. Multiplying by x uses ordinary school multiplication with a carry.
- Keep remaining=n. If the current power has fewer than remaining digits, subtract its length and multiply it by x. Once remaining falls inside the current power, its digit is at reversed-array index size−remaining. No giant concatenated string is needed.
- For x=3 the blocks are 1, 3, 9, 27, 81, 243. Their cumulative lengths are 1, 2, 3, 5, 7, 10. Position 9 is the second digit of 243, namely 4. During multiplication, each digit stores product modulo 10 while the carry stores the remaining higher digits.
Why it works
Inductively the digit array represents the next exact power of x because the multiplication is standard base-10 arithmetic. Subtracting complete block lengths preserves the target position among unprocessed digits. The selected array entry therefore equals the required digit of the correct power.
Watch out. Do not use floating-point powers or fixed-width integers. The digit array is reversed, while positions in the statement are counted from the left. Finish propagating the carry after processing the existing digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int multiplier;
int remaining;
cin>>multiplier>>remaining;
vector<int>digits(1,1);
while(remaining>static_cast<int>(digits.size())){
remaining-=static_cast<int>(digits.size());
int carry=0;
// Least-significant digit first makes carrying straightforward.
for(int&digit:digits){
int product=digit*multiplier+carry;
digit=product%10;
carry=product/10;
}
while(carry>0){
digits.push_back(carry%10);
carry/=10;
}
}
cout<<digits[digits.size()-remaining]<<'\n';
}