Giả sử chúng ta có một nhà máy sản xuất bóng, nơi chúng ta có n quả bóng được đánh số từ l đến r (cả hai) và có vô số hộp được đánh số từ 1 đến vô cùng. Vì vậy, nếu chúng ta đặt mỗi quả bóng vào hộp một số bằng tổng các chữ số của số quả bóng. (Ví dụ, quả bóng số 123 sẽ được đặt vào ô số 1 + 2 + 3 =6). Vậy nếu ta có hai giá trị l và r thì ta phải tìm số bi trong hộp có nhiều bi nhất.
Vì vậy, nếu đầu vào là l =15 r =25, thì đầu ra sẽ là 2 vì
-
Quả bóng số 15 sẽ được đưa vào bên trong 1 + 5 =6
-
Quả bóng số 16 sẽ được đưa vào bên trong 1 + 6 =7
-
Quả bóng số 17 sẽ được đưa vào bên trong 1 + 7 =8
-
Quả bóng số 18 sẽ được đưa vào bên trong 1 + 8 =9
-
Quả bóng số 19 sẽ được đưa vào bên trong 1 + 9 =10
-
Quả bóng số 20 sẽ được đưa vào bên trong 2 + 0 =2
-
Quả bóng số 21 sẽ được đưa vào bên trong 2 + 1 =3
-
Quả bóng số 22 sẽ được đưa vào bên trong 2 + 2 =4
-
Quả bóng số 23 sẽ được đưa vào bên trong 2 + 3 =5
-
Quả bóng số 24 sẽ được đưa vào bên trong 2 + 4 =6
-
Quả bóng số 25 sẽ được đưa vào bên trong 2 + 5 =7
vì vậy hộp 6 và 7 chứa tối đa số quả bóng, đó là lý do tại sao câu trả lời là 2
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
dict:=một bản đồ mới
-
đối với tôi trong phạm vi từ l đến r, hãy làm
-
tổng:=0
-
đối với mỗi chữ số j của tôi, hãy thực hiện
-
tổng:=tổng + j
-
-
nếu tổng số không có trong dict, thì
-
dict [tổng số]:=0
-
-
dict [tổng số]:=dict [tổng số] + 1
-
-
trả về giá trị tối đa cho tất cả các khóa trong dict
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(l, r):
dict={}
for i in range(l, r+1):
total=0
for j in str(i):
total += int(j)
if(total not in dict):
dict[total] = 0
dict[total] += 1
return max([dict[i] for i in dict])
l = 15
r = 25
print(solve(l, r)) Đầu vào
15, 25
Đầu ra
1