Bài 4: Số chính phương nhỏ nhất: Cho một dãy số gồm N số tự nhiên, các phần tử được đánh số từ 1 đến N. Một số tự nhiên được gọi là số chính phương nếu như nó là bình phương của một số tự nhiên khác....

Để giải bài toán này, ta có thể sử dụng một mảng để đánh dấu các số chính phương đã xuất hiện trong dãy. Ban đầu, ta khởi tạo mảng này với giá trị False. Sau đó, ta duyệt qua từng phần tử trong dãy và đánh dấu các số chính phương đã xuất hiện bằng cách gán giá trị True cho vị trí tương ứng trong mảng. Cuối cùng, ta duyệt qua mảng để tìm số chính phương nhỏ nhất không xuất hiện, và trả về kết quả. Dưới đây là đoạn code giải bài toán: ```python def tim_so_chinh_phuong_nho_nhat(N, arr): max_num = max(arr) # Tìm số lớn nhất trong dãy square_nums = [False] * (max_num + 1) # Khởi tạo mảng đánh dấu for num in arr: if num >= 0: # Chỉ xét các số không âm square_nums[num] = True # Đánh dấu số chính phương đã xuất hiện for i in range(0, max_num + 2): if not square_nums[i]: # Tìm số chính phương nhỏ nhất không xuất hiện return i # Test đoạn code với input mẫu N = 5 arr = [1, 2, 3, 4, 5] result = tim_so_chinh_phuong_nho_nhat(N, arr) print(result) # Kết quả: 9 N = 6 arr = [2, 5, 3, 9, 11, 6] result = tim_so_chinh_phuong_nho_nhat(N, arr) print(result) # Kết quả: 1 ``` Với input mẫu, kết quả là 9 và 1 tương ứng.