পাইথনে এন লোকেদের দ্বারা উল্টানো আলোর সংখ্যা গণনা করার প্রোগ্রাম

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

ব্যক্তি 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, 1]
প্লেয়ার 4 এর পরে:[1, 0, 0, 1, 1]
প্লেয়ার 5 এর পরে:[1, 0, 0, 1, 0]

শেষে 2টি লাইট অন অবস্থায় আছে

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

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

উদাহরণ

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

def solve(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

n = 5
print(solve(n))