পাইথনে n ব্যক্তিদের দ্বারা ফ্লিপ করার পরে চালু হওয়া সুইচের সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে, এবং একটি ঘরে n সুইচ রয়েছে এবং সমস্ত সুইচ বন্ধ রয়েছে। এখন n যারা ফ্লিপ করে তারা নিম্নরূপ −

• ব্যক্তি 1 সমস্ত সুইচ ফ্লিপ করে যা 1 এর গুণিতক (তাই সমস্ত সুইচ)।
• ব্যক্তি 2 ফ্লিপ সুইচ যা 2 এর গুণিতক (2, 4, 6, ...)
• ব্যক্তি i সুইচ ফ্লিপ করে যা i এর গুণিতক।

আমাদের শেষের দিকে কতগুলি সুইচ চালু হবে তা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি n =5 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন প্রাথমিকভাবে সব বন্ধ [0, 0, 0, 0, 0], ব্যক্তি 1 সবগুলিকে ফ্লিপ করেছে [1, 1, 1, 1, 1] , ব্যক্তি 2 [1, 0, 1, 0, 1] এর মত উল্টেছে, তারপর ব্যক্তি 3 করেছে [1, 0, 0, 0, 0], ব্যক্তি 4 করেছে [1, 0, 0, 1, 0]

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

• l :=0, r :=n
• যখন l <=r, do
  • মধ্য :=l +(r - l) / 2
  • যদি mid^2 <=n <(মাঝামাঝি + 1)^2, তারপর
    • মাঝে ফিরুন
  • অন্যথায় যখন n
  • r :=মধ্য
• অন্যথায়,
  • l :=মধ্য + 1

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

উদাহরণ

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