Đề bài
Bạn có thể chọn bất kỳ tập con nào của các đồng xu được cung cấp. Mỗi đồng xu chỉ được sử dụng tối đa một lần, kể cả khi có nhiều đồng xu cùng mệnh giá. Hãy tìm số nguyên dương nhỏ nhất mà không thể tạo ra bằng bất kỳ cách chọn nào.
Cài đặt hàm missing_coin_sum(coins).
Đầu vào
coins: Giá trị của các đồng xu có sẵn; các giá trị trùng lặp đại diện cho các đồng xu riêng biệt.
Đầu ra
Trả về số tiền dương nhỏ nhất không thể tạo ra.
Ràng buộc
1 ≤ số lượng đồng xu ≤ 200.000. Mỗi giá trị nằm trong khoảng từ 1 đến 1.000.000.000.
Ví dụ
Đầu vào:
coins = [1, 1, 4]
Kết quả mong đợi:
expected = 3Đầu vào:
std::vector<long long> coins = {1, 1, 4};
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long[] coins = new long[] {1, 1, 4};
Kết quả mong đợi:
long expected = 3;Giải thích
Các số tiền 1 và 2 có thể tạo ra từ các đồng xu mệnh giá 1. Không có tập con nào tạo được tổng là 3.
Đầu vào:
coins = [2, 3]
Kết quả mong đợi:
expected = 1Đầu vào:
std::vector<long long> coins = {2, 3};
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long[] coins = new long[] {2, 3};
Kết quả mong đợi:
long expected = 1;Giải thích
Không thể tạo ra số tiền 1 vì tất cả các đồng xu đều có giá trị ít nhất là 2.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Sắp xếp các đồng xu rồi xây dựng tổng nhỏ nhất có thể đạt được từ nhỏ lên lớn.
Gợi ý 2
Nếu đồng xu tiếp theo lớn hơn số nhỏ nhất chưa thể tạo, thì số đó sẽ không bao giờ ghép được.
Gợi ý 3
Các phần tử trùng nhau chỉ có ích khi chúng mở rộng vùng tổng có thể đạt mà không tạo khoảng trống.
Độ phức tạp mong đợi
O(n log n) time, O(1) extra space, excluding sorting implementation details
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.