ภาพรวมปัญหา
หาพจน์ที่ N ของอนุกรม: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...
เลข k ปรากฏ k ครั้งติดกัน
ตัวอย่าง
อินพุต
N = 6
เอาต์พุต
3
วิธีแก้ปัญหา
วิธีที่ 1: Nested Loop - O(√N)
วิธีที่ 2: สูตรทางคณิตศาสตร์ - O(1) ⭐
ตำแหน่งสุดท้ายของเลข x คือ: 1 + 2 + ... + x = x(x+1)/2
หา x ที่ทำให้: x(x-1)/2 < N ≤ x(x+1)/2
แก้สมการกำลังสอง: x² - x - 2N = 0
x = (1 + √(1 + 8N)) / 2 (ปัดขึ้น)
โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
int x = ceil((1 + sqrt(1 + 8.0 * n)) / 2);
return x;
}
int main() {
int n = 12;
cout << "The series is 1, 2, 2, 3, 3, 3, 4, 4, ...\n";
cout << n << "th term of the series is " << findNthTerm(n);
return 0;
}
เอาต์พุต
The series is 1, 2, 2, 3, 3, 3, 4, 4, ... 12th term of the series is 5
สรุป
ใช้สูตร Quadratic Formula หา x โดยตรง O(1) เร็วที่สุด
