পাইথনে n ব্যক্তি দিয়ে সুইচ ফ্লিপে অন সমস্যা সমাধান

n সংখ্যক সুইচ আছে যেগুলো প্রাথমিকতে অফ। n জন ব্যক্তি নিজের সংখ্যার গুণিতক সুইচগুলো ফ্লিপ করে। শেষে কতগুলো সুইচ অন থাকবে তা বের করতে হবে।

উদাহরণ: n = 5 হলে আউটপুট ২।

সমাধানের ধাপসমূহ

• বাইনারি সার্চ ব্যবহার করে sqrt(n) এর ফ্লোর মান বের করুন
• l := 0, r := n
• যবত l <= r:
  • mid := l + (r-l)//2
  • যদি mid^2 <= n < (mid+1)^2 হয় তবে mid ফেরত দিন
  • অন্যথায় বাইনারি সার্চ চালিয়ে থাকুন

উদাহরণ কোড

class Solution:
    def solve(self, n):
        l, r = 0, n
        while l <= r:
            mid = l + (r - l) // 2
            if mid * mid <= n < (mid + 1) * (mid + 1):
                return mid
            elif n < mid * mid:
                r = mid
            else:
                l = mid + 1

ob = Solution()
n = 5
print(ob.solve(n))

ইনপুট

5

আউটপুট

2