Salary Digit
Autumn Tournament (2013)
Submission name: salary.cpp
Problem summary
Concatenate the decimal cubes 1³, 2³, 3³, ... without separators. Find the digit in position k, counting from 1. In the story, this digit determines a tax percentage.
Input
One integer k.
Output
The digit at position k.
Constraints
1 ≤ k ≤ 1000000.
Worked example
Original statement sample.
Input
7
Output
1
Solution analysis
- Generate one cube at a time instead of constructing the entire infinite digit string. Convert each cube to its decimal representation. The variable remaining is the position still needed among the current and later cubes.
- If remaining exceeds the current cube’s number of digits, skip that complete block and subtract its length. Otherwise the answer is the character at index remaining−1. This converts the problem’s 1-based position to a 0-based string index.
- The first blocks are 1, 8, 27, 64, 125. For k=7, skip lengths 1, 1, 2, 2, leaving position 1 in 125; therefore the answer is 1. For k=3, the first digit of 27 is 2.
Why it works
Before each iteration, remaining identifies the same target digit after removing all earlier cube blocks. Skipping a block preserves that invariant. When remaining lies inside the current block, indexing that block therefore returns precisely the required digit.
Watch out. Positions start at 1. Calculate month³ in long long; int multiplication can overflow well before the largest allowed k.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int remaining;
cin>>remaining;
for(long long month=1;;++month){
string digits=to_string(month*month*month);
if(remaining<=static_cast<int>(digits.size())){
cout<<digits[remaining-1]<<'\n';
return 0;
}
// Skip an entire cube, preserving the target's relative position.
remaining-=static_cast<int>(digits.size());
}
}