หาค่า N สูงสุดที่ผลรวมกำลังสองของ N จำนวนธรรมชาติแรกไม่เกิน X ใน C++

แนวคิด

เมื่อได้รับจำนวนเต็ม X งานของเราคือหาค่า N สูงสุดที่ทำให้ผลรวมของกำลังสองของ N จำนวนธรรมชาติแรกไม่เกิน X

อินพุต

X = 7

เอาต์พุต

2

2 คือค่า N สูงสุดที่เป็นไปได้ เพราะถ้า N = 3 ผลรวมของอนุกรมจะเกิน X คือ 1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14

อินพุต

X = 27

เอาต์พุต

3

3 คือค่า N สูงสุดที่เป็นไปได้ เพราะถ้า N = 4 ผลรวมของอนุกรมจะเกิน X คือ 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30

วิธีการ

วิธีง่าย − วิธีง่ายคือรันลูปจาก 1 จนถึง N สูงสุดที่ S(N) ≤ X ในที่นี้ S(N) หมายถึงผลรวมของกำลังสองของ N จำนวนธรรมชาติแรก ผลรวมของกำลังสองของ N จำนวนธรรมชาติแรกกำหนดโดยสูตร S(N) = N * (N + 1) * (2 * N + 1) / 6

ควรสังเกตว่า Time Complexity ของวิธีนี้คือ O(N)

วิธีที่มีประสิทธิภาพ − เราสามารถใช้วิธีแก้ปัญหาอีกวิธีหนึ่งที่มีประสิทธิภาพซึ่งอิงจาก Binary Search

เราทำตามอัลกอริทึมด้านล่างซึ่งอธิบายทีละขั้นตอน −

• เริ่ม binary search ในอาร์เรย์ที่ใหญ่กว่า และได้ mid เป็น (low + high) / 2

• พบว่าถ้าค่าจากทั้งสองอาร์เรย์เท่ากัน ตัวเลขต้องอยู่ในส่วนขวา จึงตั้ง low เป็น mid

• มิฉะนั้น ตั้ง high เป็น mid เพราะตัวเลขต้องอยู่ในส่วนซ้ายของอาร์เรย์ที่ใหญ่กว่า ถ้า mid element ไม่เท่ากัน

ควรสังเกตว่า Time Complexity ของวิธีนี้คือ O(log N)

ตัวอย่างโค้ด

// การนำไปใช้ C++ ของวิธีการ #include <bits/stdc++.h> using namespace std; #define ll long long // ฟังก์ชันแสดงการคืนผลรวมของกำลังสอง // ของ N1 จำนวนธรรมชาติแรก ll squareSum(ll N1){    ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;    return sum1; } // ฟังก์ชันแสดงการคืนค่า N สูงสุดที่ // ผลรวมของกำลังสองของ N // จำนวนธรรมชาติแรกไม่เกิน X ll findMaxN(ll X){    ll low1 = 1, high1 = 100000;    int N1 = 0;    while (low1 <= high1) {       ll mid1 = (high1 + low1) / 2;       if (squareSum(mid1) <= X) {          N1 = mid1;          low1 = mid1 + 1;       }       else          high1 = mid1 - 1;    }    return N1; } // โค้ดหลัก int main(){    ll X = 27;    cout << findMaxN(X);    return 0; }

เอาต์พุต

3