Đề bài
Số tam giác thứ n là 1 + 2 + … + n. Có một công thức giúp tránh phải lặp với các giá trị đầu vào rất lớn. Số tam giác thứ 0 là 0.
Hãy cài đặt triangular_number(n).
Đầu vào
n: Một số nguyên không âm.
Đầu ra
Trả về 1 + 2 + … + n.
Ràng buộc
0 ≤ n ≤ 1.000.000.000. Kết quả nằm trong phạm vi của số nguyên có dấu 64-bit.
Ví dụ
Đầu vào:
n = 10
Kết quả mong đợi:
expected = 55
Đầu vào:
long long n = 10;
Kết quả mong đợi:
long long expected = 55;
Đầu vào:
long n = 10;
Kết quả mong đợi:
long expected = 55;
Giải thích
1 + 2 + … + 10 = 55.
Đầu vào:
n = 0
Kết quả mong đợi:
expected = 0
Đầu vào:
long long n = 0;
Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long n = 0;
Kết quả mong đợi:
long expected = 0;
Giải thích
Không có số nào để cộng, nên tổng là 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tìm quy luật trong tổng dồn thay vì cộng từng số một.
Gợi ý 2
Dùng công thức cấp số cộng dựa trên số hạng đầu và cuối để khỏi phải lặp.
Gợi ý 3
Cẩn thận với trường hợp 0, và đảm bảo phép tính không vượt quá giới hạn 64-bit.
Độ phức tạp mong đợi
thời gian O(1), bộ nhớ phụ O(1)