โจทย์
ให้นับจำนวนจำนวนเต็มตั้งแต่ left ถึง right (รวมทั้งสองขอบเขต) ที่ไม่มีเลขหลักฐานข้างเคียงที่เท่ากันเลย โดยใช้รูปแบบเลขฐานสิบปกติและต้องไม่มีศูนย์นำหน้า ศูนย์และตัวเลขหลักเดียวทั้งหมดถือว่าเข้าเงื่อนไขนี้
ให้เขียนฟังก์ชัน counting_numbers(left, right)
อินพุต
left: ค่าต่ำสุดที่อนุญาต
right: ค่าสูงสุดที่อนุญาต
เอาต์พุต
ให้คืนค่าจำนวนตัวเลขที่เข้าเงื่อนไขข้างต้น
เงื่อนไข
0 ≤ left ≤ right ≤ 10¹⁸ ช่วงค่าที่กำหนดอาจกว้างเกินกว่าจะตรวจสอบทีละจำนวนได้
ตัวอย่าง
อินพุต:
left = 10
right = 15
ผลลัพธ์ที่คาดหวัง:
expected = 5
อินพุต:
long long left = 10;
long long right = 15;
ผลลัพธ์ที่คาดหวัง:
long long expected = 5;
อินพุต:
long left = 10;
long right = 15;
ผลลัพธ์ที่คาดหวัง:
long expected = 5;
คำอธิบาย
มีเพียง 11 เท่านั้นที่มีเลขข้างเคียงซ้ำกัน อีกห้าตัวเลขที่เหลือเข้าเงื่อนไขทั้งหมด
อินพุต:
left = 0
right = 9
ผลลัพธ์ที่คาดหวัง:
expected = 10
อินพุต:
long long left = 0;
long long right = 9;
ผลลัพธ์ที่คาดหวัง:
long long expected = 10;
อินพุต:
long left = 0;
long right = 9;
ผลลัพธ์ที่คาดหวัง:
long expected = 10;
คำอธิบาย
ทั้งสิบค่ามีเพียงหลักเดียว จึงไม่มีเลขข้างเคียงซ้ำกันเลย
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
นับจำนวนที่ถูกต้องถึงแต่ละปลายช่วง แล้วลบกันเพื่อได้คำตอบของช่วง
คำใบ้ 2
Digit DP เหมาะมาก เพราะความถูกต้องขึ้นกับเลขที่ติดกันและว่ายังไม่เริ่มเลขจริงหรือไม่
คำใบ้ 3
เลข 0 นำหน้าต้องจัดการพิเศษ เพื่อให้นับเลขที่สั้นกว่าถูกต้อง
ความซับซ้อนที่คาดหวัง
เวลา O(k * 10 * states), หน่วยความจำเพิ่ม O(k * states)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน