Ctrl K

Letter on a Self-Copying Tape

Medium
A typewriter reads a pattern string pattern from left to right and prints onto a tape: - a letter is appended to the end of the tape; - a digit d turns the whole current tape into d copies of itself back to back (it appends d - 1 more copies). The tape can get astronomically long, so printing it out is not an option. Return the k-th letter of the finished tape (1-based).
Example 1
pattern='ab3c2', k=8 → 'a'

The tape grows as ab → ababab → abababc → abababcabababc. The 8th letter is a.

Example 2
pattern='xy2z9', k=45 → 'z'

After xy2z the tape holds xyxyz (5 letters); after 9 it holds 45. The last of them is z.

Example 3
pattern='q777777', k=100000 → 'q'

The tape is all qs, 7⁶ = 117649 of them, so every letter is q.

Constraints
  • 2 ≤ len(pattern) ≤ 100
  • pattern consists of lowercase English letters and digits 2 to 9 and starts with a letter
  • 1 ≤ k ≤ 10⁹
  • k does not exceed the tape length, and the tape is shorter than 2⁶³
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsTidy a Folder Route MediumFour-Operation Calculator MediumEvery Letter Once MediumChecking a Tree Record With Hash Marks MediumLongest Path to a File Medium
loading Python…
Input
pattern='ab3c2', k=8
Expected
'a'

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.