แนวคิด
สำหรับจำนวนเต็ม X ที่กำหนด งานของเราคือกำหนดค่าสูงสุด N เพื่อให้ผลรวมของจำนวนธรรมชาติ N ตัวแรกไม่ควรเกิน X
อินพุต
X = 7
ผลลัพธ์
2
2 คือค่าสูงสุดที่เป็นไปได้ของ N เนื่องจากสำหรับ N =3 ผลรวมของอนุกรมจะเกิน Xi.e 1^2 + 2^2 + 3^2 =1 + 4 + 9 =14
อินพุต
X = 27
ผลลัพธ์
3
3 คือค่าที่เป็นไปได้สูงสุดของ N เพราะสำหรับ N =4 ผลรวมของอนุกรมจะเกิน X.e 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
ควรสังเกตว่าความซับซ้อนของเวลาของวิธีการนี้คือ O(N)
แนวทางที่มีประสิทธิภาพ − เราสามารถใช้โซลูชันอื่นที่มีประสิทธิภาพซึ่งอิงตามแนวทางการค้นหาแบบไบนารี
เราปฏิบัติตามอัลกอริทึมด้านล่างซึ่งอธิบายทีละขั้นตอน -
-
เริ่มการค้นหาไบนารีในอาร์เรย์ที่ใหญ่กว่าและรับค่ากลางเป็น (ต่ำ + สูง) / 2
-
จะเห็นได้ว่าหากค่าจากอาร์เรย์ทั้งสองมีค่าเท่ากัน องค์ประกอบจะต้องอยู่ทางด้านขวา ดังนั้นให้ทำเครื่องหมายที่ระดับต่ำเป็นระดับกลาง
-
มิฉะนั้นให้ทำเครื่องหมายสูงเป็นระดับกลางเนื่องจากองค์ประกอบต้องอยู่ในด้านซ้ายของอาร์เรย์ที่ใหญ่กว่าหากองค์ประกอบกลางไม่เหมือนกัน
ควรสังเกตว่าความซับซ้อนของเวลาของวิธีการนี้คือ O(log N)
ตัวอย่าง
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Shows function to return the sum of the squares
// of first N1 natural numbers
ll squareSum(ll N1){
ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
return sum1;
}
// Shows function to return the maximum N such that
// the sum of the squares of first N
// natural numbers is not more than 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;
}
// Driver code
int main(){
ll X = 27;
cout << findMaxN(X);
return 0;
} ผลลัพธ์
3
