Chương trình tìm phần tử trùng lặp từ n+1 số trong khoảng 1 đến n trong Python

Cho danh sách nums độ dài n+1 chứa các số từ 1 đến n. Theo nguyên lý cái bồ câu, chắc chắn có ít nhất một số trùng. Tìm số đó.

Ví dụ

Đầu vào: [2, 1, 4, 3, 3].
Đầu ra: 3.

Thuật toán

1. Tính tổng lý thuyết của 1..n: temp = n*(n+1)/2 (với n = len(nums)-1).
2. Tính tổng thực tế temp_sum = sum(nums).
3. Trả về temp_sum - temp.

Mã nguồn Python

class Solution:
    def solve(self, nums):
        l = len(nums)
        temp = l*(l-1)//2
        temp_sum = sum(nums)
        return temp_sum - temp

ob = Solution()
print(ob.solve([2, 1, 4, 3, 3]))

Đầu vào / Đầu ra

Input: [2, 1, 4, 3, 3]
Output: 3