โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

เลขโดดของค่าคงตัวแชมเปอร์โนว์น (Champernowne)

หาเลขโดดในตำแหน่งที่กำหนดของสตริง 123456789101112... ที่ได้จากการเขียนจำนวนนับเรียงต่อกัน

สิ่งที่คุณจะได้เรียนรู้

  • นับจำนวนหลักที่จำนวนแต่ละความยาวใช้
  • หาจำนวนและเลขโดดจากตำแหน่ง
  • ใช้การคำนวณ 64 บิตอย่างปลอดภัย

โจทย์

ให้เขียนจำนวนเต็มบวกเรียงต่อกันไปเรื่อย ๆ จะได้ 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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก