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