Đề bài
Viết các số nguyên dương nối tiếp nhau: 123456789101112131415... Vị trí 1 là chữ số 1, vị trí 10 là chữ số 1 của số 10, vị trí 11 là chữ số 0 của số 10. Với mỗi vị trí được hỏi, hãy tìm chữ số ở đó. Các vị trí lớn hơn rất nhiều so với một chuỗi bạn có thể dựng được, nên hãy bỏ qua cả khối những số có cùng số chữ số (9 số có một chữ số, 90 số có hai chữ số, 900 số có ba chữ số, ...).
Hãy viết champernowne_digits(positions).
Đầu vào
positions: Các vị trí trong chuỗi chữ số, đếm từ 1.
Đầu ra
Trả về chữ số ở từng vị trí, theo đúng thứ tự của đầu vào. Đầu vào rỗng thì trả về danh sách rỗng.
Ràng buộc
0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15
Ví dụ
Đầ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
Chuỗi bắt đầu bằng 1 2 3 4 5 6 7 8 9 1 0 1 1, nên các chữ số là [1, 9, 1, 0].
Đầ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
Vị trí 15 là chữ số 2 của số 12. Các vị trí từ 10 đến 189 chứa các số từ 10 đến 99, nên vị trí 190 là chữ số đầu tiên của 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
Các số có d chữ số chiếm tổng cộng 9 × 10^(d − 1) × d vị trí.
Gợi ý 2
Trừ dần cả khối cho đến khi vị trí rơi vào bên trong một khối.
Gợi ý 3
Trong khối đó, (position − 1) / d cho biết là số nào và (position − 1) % d cho biết là chữ số nào.
Độ phức tạp mong đợi
thời gian O(m × log P) với m vị trí, bộ nhớ phụ O(m)
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.