CTDL&GT bài 14.B3 CTDL&GT bài Số bị thiếu


LÀM BÀI

Points: 15
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Số bị thiếu

Trong một buổi giao lưu với MC, FullHouse Dev được thử thách giải một bài toán thú vị. MC đưa ra một mảng số và yêu cầu FullHouse Dev tìm ra số bị thiếu lớn nhất có thể. Với tinh thần nhiệt huyết, FullHouse Dev bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\). Họ có thể giảm bất kỳ phần tử nào của mảng đi 1. Thao tác này có thể được lặp lại nhiều lần. Một số được coi là bị thiếu nếu nó là số dương nhỏ nhất là bội của 2 mà không có mặt trong mảng \(A\). Nhiệm vụ của FullHouse Dev là tìm ra số bị thiếu lớn nhất sau khi thực hiện tất cả các phép giảm có thể cho các phần tử.

INPUT FORMAT:
  • Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
  • Dòng đầu tiên của mỗi test case chứa số nguyên \(N\) - kích thước của mảng.
  • Dòng thứ hai của mỗi test case chứa \(N\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).
OUTPUT FORMAT:
  • In ra kết quả cho mỗi test case trên một dòng mới.
Ràng buộc:
  • \(1 \leq T \leq 100\)
  • \(1 \leq N \leq 10^5\)
  • \(1 \leq A[i] \leq 10^9\)
Ví dụ
INPUT
2
6
1 3 3 3 6 7
3
3 0 2
OUTPUT
8
4
Giải thích
  • Ở test case đầu tiên, FullHouse Dev có thể giảm phần tử thứ 2 xuống 2, phần tử thứ 3 xuống 4 và phần tử thứ 4 xuống 6. Mảng sau khi giảm sẽ là [1, 2, 4, 6, 6, 7]. Số dương nhỏ nhất là bội của 2 không có trong mảng đã sửa đổi là 8, do đó số bị thiếu là 8.
  • Ở test case thứ hai, dù có giảm hay không, chỉ có thể có 2 là bội duy nhất của 2 trong mảng, do đó số bị thiếu là 4.

Với sự thông minh và nhanh nhẹn, FullHouse Dev đã giải quyết thành công bài toán, khiến MC vô cùng ấn tượng với khả năng tư duy logic của họ.


Comments

There are no comments at the moment.

Zalo