Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Champernowne Digits

Find digits at given positions of the string 123456789101112... made by writing out the counting numbers.

Bạn sẽ học được gì

  • Count digits used by numbers of each length
  • Locate a number and digit from a position
  • Use 64-bit arithmetic safely

Đề bài

Xem bản dịch

Write the positive integers one after another: 123456789101112131415... Position 1 holds 1, position 10 holds the 1 of 10, position 11 the 0 of 10. For each requested position, find the digit there. The positions go far past what you could build as a string: skip whole blocks of numbers with the same number of digits (9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, ...).

Implement champernowne_digits(positions).

Input

positions: Positions in the digit string, counting from 1.

Output

Return the digit at each position, in the same order as the input. An empty input returns an empty list.

Ràng buộc

0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15

Ví dụ

Ví dụ 1
Đầu vào:
positions = [1, 9, 10, 11]

Kết quả mong đợi:
expected = [1, 9, 1, 0]
Đầu vào:
std::vector<long long> positions = {1, 9, 10, 11};

Kết quả mong đợi:
std::vector<long long> expected = {1, 9, 1, 0};
Đầu vào:
long[] positions = new long[] {1, 9, 10, 11};

Kết quả mong đợi:
long[] expected = new long[] {1, 9, 1, 0};

Giải thích

The string starts 1 2 3 4 5 6 7 8 9 1 0 1 1, so the digits are [1, 9, 1, 0].

Ví dụ 2
Đầu vào:
positions = [15, 190]

Kết quả mong đợi:
expected = [2, 1]
Đầu vào:
std::vector<long long> positions = {15, 190};

Kết quả mong đợi:
std::vector<long long> expected = {2, 1};
Đầu vào:
long[] positions = new long[] {15, 190};

Kết quả mong đợi:
long[] expected = new long[] {2, 1};

Giải thích

Position 15 is the 2 of 12. Positions 10 to 189 hold 10 to 99, so 190 is the first digit of 100: [2, 1].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Numbers with d digits take 9 × 10^(d − 1) × d positions in total.

Gợi ý 2

Subtract whole blocks until the position falls inside one.

Gợi ý 3

Within the block, (position − 1) / d tells you which number and (position − 1) % d which digit.

Độ phức tạp mong đợi

O(m × log P) time for m positions, O(m) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.