Chương trình tìm chỉ số bắt đầu của trẻ nhận bóng bay cuối cùng trong Python

Có n trẻ đứng thành vòng tròn (chỉ số 0 đến n-1). Phân phát bóng bay bắt đầu từ trẻ thứ k (0-indexed), trẻ nhận bóng bay rời khỏi vòng. Mỗi lần đếm k trẻ theo chiều kim đồng hồ, trẻ đó nhận bóng và rời đi. Tìm chỉ số ban đầu của trẻ nhận bóng bay cuối cùng.

Ví dụ

n = 3, k = 2

Vòng: [0, 1, 2]

Lần 1: đếm 2 → trẻ 2 rời, còn [0, 1]

Lần 2: đếm 2 từ 0 → trẻ 0 rời, còn [1]

Kết quả: 1

Thuật toán (Mô phỏng / Josephus Problem biến thể)

1. Tạo danh sách arr = list(range(n)).
2. idx = 0 (vị trí bắt đầu đếm).
3. Khi len(arr) > 1:
   • remove = (idx + k) % len(arr)
   • Xóa arr[remove]
   • idx = remove (tiếp tục đếm từ vị trí sau)
4. Trả về arr[0].

Triển khai Python

class Solution:
    def solve(self, n, k):
        arr = list(range(n))
        idx = 0
        while len(arr) > 1:
            remove = (idx + k) % len(arr)
            del arr[remove]
            idx = remove
        return arr[0]

# Test
ob = Solution()
print(ob.solve(3, 2))   # 1
print(ob.solve(5, 3))   # 3
print(ob.solve(7, 2))   # 6

Độ phức tạp

• Thời gian: O(n²) do xóa phần tử list O(n) lặp n lần.
• Không gian: O(n).

Có thể tối ưu về O(n) hoặc O(k log n) bằng công thức toán học Josephus hoặc cây đoạn / BIT.