โจทย์
จำนวนฮาร์ชาด (Harshad number) หรือที่เรียกอีกชื่อว่า จำนวนนิเวน (Niven number) คือจำนวนเต็มบวกที่หารด้วยผลรวมของเลขโดดทุกหลักของตัวเองลงตัว เช่น 18 มีผลรวมของหลักเป็น 1 + 8 = 9 และ 18 ÷ 9 = 2 ไม่มีเศษ ดังนั้น 18 เป็นจำนวนฮาร์ชาด
จงเขียน harshad_number(n)
อินพุต
n: จำนวนที่ต้องการตรวจสอบ
เอาต์พุต
คืนค่า true ถ้า n หารด้วยผลรวมของเลขโดดฐานสิบของตัวเองลงตัว มิฉะนั้นคืนค่า false
เงื่อนไข
1 ≤ n ≤ 10^18
ตัวอย่าง
อินพุต:
n = 156
ผลลัพธ์ที่คาดหวัง:
expected = True
อินพุต:
long long n = 156;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
อินพุต:
long n = 156;
ผลลัพธ์ที่คาดหวัง:
bool expected = true;
คำอธิบาย
ผลรวมของหลักคือ 1 + 5 + 6 = 12 และ 156 = 12 × 13 คำตอบจึงเป็น true
อินพุต:
n = 19
ผลลัพธ์ที่คาดหวัง:
expected = False
อินพุต:
long long n = 19;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
อินพุต:
long n = 19;
ผลลัพธ์ที่คาดหวัง:
bool expected = false;
คำอธิบาย
ผลรวมของหลักคือ 1 + 9 = 10 และ 19 ไม่ใช่พหุคูณของ 10 คำตอบจึงเป็น false
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
หาผลรวมของหลักก่อน โดยใช้สำเนาของ n
คำใบ้ 2
n เป็นจำนวนฮาร์ชาดเมื่อเศษจากการหาร n ด้วยผลรวมของหลักเป็น 0
คำใบ้ 3
ผลรวมของหลักของจำนวนบวกไม่มีทางเป็น 0 การหารจึงปลอดภัย
ความซับซ้อนที่คาดหวัง
เวลา O(d) เมื่อมี d หลัก, หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน