সর্বাধিক N বের করুন যাতে প্রথম N প্রাকৃতিক সংখ্যার বর্গক্ষেত্রের যোগফল পাইথনে X-এর বেশি না হয়

ধরুন আমাদের একটি প্রদত্ত পূর্ণসংখ্যা X আছে, আমাদের সর্বাধিক মান N খুঁজে বের করতে হবে যাতে প্রথম N প্রাকৃতিক সংখ্যার যোগফল X মানের বেশি না হয়।

সুতরাং, যদি ইনপুটটি X =7 এর মত হয়, তাহলে আউটপুট হবে 2 কারণ 2 হল N এর সর্বোচ্চ সম্ভাব্য মান, N =3 এর জন্য, সিরিজের যোগফল X =7 ছাড়িয়ে যাবে তাই, 1^2 + 2^ 2 + 3^2 =1 + 4 + 9 =14।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন সংজ্ঞায়িত করুন sum_of_squares()। এটি N
লাগবে
res :=(N *(N + 1) *(2 * N + 1)) / 6
রিটার্ন রিটার্ন
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
কম :=1
উচ্চ :=100000
N :=0
যখন কম -=উচ্চ, করুন
- মধ্য :=(উচ্চ + নিম্ন) / 2
- যদি sum_of_squares(mid) −=X হয়, তাহলে
  - N :=মধ্য
  - নিম্ন :=মধ্য + 1
- অন্যথায়,
  - উচ্চ :=মধ্য - 1
ফেরত N

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def sum_of_squares(N):
   res = (N * (N + 1) * (2 * N + 1)) // 6
   return res
def get_max(X):
   low, high = 1, 100000
   N = 0
   while low <= high:
      mid = (high + low) // 2
      if sum_of_squares(mid) <= X:
         N = mid
         low = mid + 1
      else:
         high = mid - 1
   return N
X = 7
print(get_max(X))

ইনপুট

আউটপুট