สมมติว่าเรามีตัวเลข n เราต้องหาตัวหารของ n ที่ "ดีที่สุด" ตามเงื่อนไข: ระหว่างสองตัวเลข p และ q ตัวที่ผลรวมหลัก (Digit Sum) มากกว่าจะ "ดีกว่า" หากผลรวมหลักเท่ากัน ตัวเลขที่น้อยกว่าจะดีกว่า
ตัวอย่าง n = 180 ตัวหารคือ [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180] ผลรวมหลักมากที่สุดคือ 9 (จาก 9, 18, 36, 45, 90, 180) แต่ 9 น้อยที่สุด จึงเป็นคำตอบ
ขั้นตอนการแก้ปัญหา
- div := 1, md := 1
- for i ในช่วง 2 ถึง n:
- k := i
- ถ้า n % i > 0: ข้าม
- s := 0
- while k > 0: s += k % 10; k //= 10
- ถ้า s > md: md = s, div = i
- คืนค่า div
ตัวอย่างโค้ด
def solve(n):
div = 1
md = 1
for i in range(2, n + 1):
k = i
if n % i > 0:
continue
s = 0
while k > 0:
s += k % 10
k //= 10
if s > md:
md = s
div = i
return div
n = 180
print(solve(n))
อินพุต
180
เอาต์พุต
9
