Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Số tam giác

Cộng các số nguyên từ 1 đến n.

Bạn sẽ học được gì

  • Cộng các số từ 1 đến n bằng vòng lặp
  • Học công thức n × (n + 1) / 2
  • So sánh vòng lặp với công thức thời gian hằng

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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)

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.