Kiểm tra xem ít nhất một nửa mảng có thể giảm xuống 0 bằng cách thực hiện một số hoạt động trong Python

Giả sử, chúng ta được cung cấp một danh sách kích thước n chứa các số nguyên dương và một số nguyên dương m khác. Giả sử, chúng ta hiện đang ở bên trong một vòng lặp và trong mỗi lần lặp, chúng ta giảm giá trị của một số phần tử trong mảng đi 1 và tăng giá trị của các phần tử còn lại lên m. Chúng ta phải tìm hiểu xem một nửa hoặc nhiều phần tử của danh sách có biến thành không sau một số lần lặp lại hay không. Chúng tôi trả về True nếu có thể và False nếu không.

Vì vậy, nếu đầu vào giống như input_list =[10, 18, 35, 5, 12], m =4, thì đầu ra sẽ là True.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• frequency_list:=một danh sách mới có kích thước m + 1 được khởi tạo bằng 0
• i:=0
• while i

• frequency_list [input_list [i] mod (m + 1)]:=

  frequency_list [input_list [i] mod (m + 1)] + 1

• i:=i + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(input_list, m):
   frequency_list = [0] * (m + 1)
   i = 0
   while(i < len(input_list)):
      frequency_list[(input_list[i] % (m + 1))] += 1
      i += 1
   i = 0
   while(i <= m):
      if(frequency_list[i] >= (len(input_list)/ 2)):
         break
      i += 1
   if (i <= m):
      return True
   else:
      return False
input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4))

Đầu vào

[10, 18, 35, 5, 12], 4

Đầu ra

True