ปัญหา
กำหนด List จำนวนเต็มบวก และจำนวนเต็มบวก m ทุก Iteration: เลือกบาง元素 -1, อื่นๆ +m ถามว่าสามารถทำให้ ≥ครึ่งหนึ่งกลายเป็น 0 ได้หรือไม่
ตัวอย่าง: [10, 18, 35, 5, 12], m=4 → True
แนวทางแก้ปัญหา
สังเกตว่า Operation: -1 หรือ +m → modulo (m+1) ไม่เปลี่ยนแปลง ดังนั้นนับ frequency ของ val % (m+1) หากมีค่า remainder ใด ≥ n/2 → True
ตัวอย่างโค้ด
def solve(input_list, m):
frequency_list = [0] * (m + 1)
for val in input_list:
frequency_list[val % (m + 1)] += 1
for freq in frequency_list:
if freq >= len(input_list) / 2:
return True
return False
input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4)) # Trueอินพุต / เอาต์พุต
Input: [10, 18, 35, 5, 12], 4 Output: True
