โจทย์
ให้เขียนจำนวนเต็มบวกเรียงต่อกันไปเรื่อย ๆ จะได้ 123456789101112131415... ตำแหน่งที่ 1 คือ 1 ตำแหน่งที่ 10 คือเลข 1 ของ 10 และตำแหน่งที่ 11 คือเลข 0 ของ 10 สำหรับแต่ละตำแหน่งที่ถาม ให้หาเลขโดดที่อยู่ตรงนั้น ตำแหน่งเหล่านี้ไกลเกินกว่าจะสร้างเป็นสตริงจริงได้ ให้ข้ามทีละกลุ่มของจำนวนที่มีจำนวนหลักเท่ากัน (จำนวนหนึ่งหลัก 9 ตัว จำนวนสองหลัก 90 ตัว จำนวนสามหลัก 900 ตัว ...)
จงเขียนฟังก์ชัน champernowne_digits(positions)
อินพุต
positions: ตำแหน่งในสตริงของเลขโดด เริ่มนับจาก 1
เอาต์พุต
คืนค่าเลขโดดที่แต่ละตำแหน่ง เรียงตามลำดับเดียวกับอินพุต ถ้าอินพุตว่างให้คืนค่ารายการว่าง
เงื่อนไข
0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15
ตัวอย่าง
อินพุต:
positions = [1, 9, 10, 11]
ผลลัพธ์ที่คาดหวัง:
expected = [1, 9, 1, 0]
อินพุต:
std::vector<long long> positions = {1, 9, 10, 11};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {1, 9, 1, 0};
อินพุต:
long[] positions = new long[] {1, 9, 10, 11};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {1, 9, 1, 0};
คำอธิบาย
สตริงเริ่มต้นด้วย 1 2 3 4 5 6 7 8 9 1 0 1 1 เลขโดดจึงเป็น [1, 9, 1, 0]
อินพุต:
positions = [15, 190]
ผลลัพธ์ที่คาดหวัง:
expected = [2, 1]
อินพุต:
std::vector<long long> positions = {15, 190};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {2, 1};
อินพุต:
long[] positions = new long[] {15, 190};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {2, 1};
คำอธิบาย
ตำแหน่งที่ 15 คือเลข 2 ของ 12 ตำแหน่งที่ 10 ถึง 189 เป็นของจำนวน 10 ถึง 99 ดังนั้นตำแหน่งที่ 190 คือเลขโดดตัวแรกของ 100 คำตอบจึงเป็น [2, 1]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
จำนวนที่มี d หลักใช้ตำแหน่งรวมทั้งหมด 9 × 10^(d − 1) × d ตำแหน่ง
คำใบ้ 2
ลบออกทีละกลุ่มจนกว่าตำแหน่งจะตกอยู่ในกลุ่มใดกลุ่มหนึ่ง
คำใบ้ 3
ภายในกลุ่มนั้น (position − 1) / d บอกว่าเป็นจำนวนใด และ (position − 1) % d บอกว่าเป็นเลขโดดตัวใด
ความซับซ้อนที่คาดหวัง
เวลา O(m × log P) โดย m คือจำนวนตำแหน่ง, หน่วยความจำเพิ่ม O(m)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน