K-th Digit in a Concatenated Number String

Interview

Time limit2sMemory limit64 MB

Summary
Given N and k, find the k-th digit in the concatenation of integers 1 through N, or -1 if the string is shorter than k.
Level

Medium4 of 10

Topics
Math, Binary search, Implementation
Solved
No attempts yet

Problem

Write all integers from 1 through N in order, without spaces, to form one long digit string.

1234567891011121314151617181920212223...

Find the digit that appears in the k-th position from the beginning of this string.

Input

The first line contains two integers N and k, separated by one or more spaces.

  • 1 ≤ N ≤ 100,000,000
  • 1 ≤ k ≤ 1,000,000,000

Output

If the concatenated string is shorter than k digits, print -1. Otherwise, print the digit at the k-th position from the beginning.

Examples1

  1. Example 1

    Input
    20 23
    Expected output
    6