পাইথনে X-এর চেয়ে বড় না হওয়া প্রাকৃতিক সংখ্যার বর্গের যোগফলের সর্বোচ্চ N বের করা

ধরা যাক একটি ইন্টিজার X দেওয়া আছে। আমাদের সর্বোচ্চ N বের করতে হবে যাতে প্রথম Nটি প্রাকৃতিক সংখ্যার বর্গের যোগফল X-র চেয়ে বড় না হয়।

যেমন, X=7 হলে আউটপুট 2, কারণ N=3 হলে 1^2+2^2+3^2=14 > 7।

সমাধানের ধাপসমূহ (বাইনারি সার্চ)

• sum_of_squares(N) = N(N+1)(2N+1)/6
• low=1, high=100000, N=0
• while low <= high:
  • mid = (low+high)//2
  • যদি sum_of_squares(mid) <= X: N=mid; low=mid+1
  • অন্যথায়: high=mid-1
• return N

উদাহরণ

def sum_of_squares(N):
    return (N * (N + 1) * (2 * N + 1)) // 6
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))

ইনপুট

7

আউটপুট

2