একটি সংখ্যা n দেওয়া আছে। ধরুন একটি রুমে nটি টগল সুইচ এবং nজন মানুষ আছে। মানুষগুলো নিম্নরূপ সুইচ ফ্লিপ করে:
- ১ম মানুষ: সব সুইচ ফ্লিপ করে।
- ২য় মানুষ: ২-এর গুণিতক সুইচ ফ্লিপ করে (২, ৪, ৬, ...)।
- i-তম মানুষ: i-এর গুণিতক সুইচ ফ্লিপ করে।
শেষে কতটি সুইচ অন (ON) অবস্থায় থাকবে তা বের করুন।
উদাহরণ: n = 5 হলে আউটপুট 2।
শুরু: [0, 0, 0, 0, 0] ১ম মানুষ: [1, 1, 1, 1, 1] ২য় মানুষ: [1, 0, 1, 0, 1] ৩য় মানুষ: [1, 0, 0, 0, 1] ৪র্থ মানুষ: [1, 0, 0, 1, 1] ৫ম মানুষ: [1, 0, 0, 1, 0] শেষে ২টি অন।
গাণিতিক পর্যবেক্ষণ
একটি সুইচ k ততবার ফ্লিপ হবে যতটি k-এর ডিভাইজার আছে। ডিভাইজার সংখ্যা বিজোড় হলে সুইচ অন থাকবে। শুধু পারফেক্ট স্কয়ার সংখ্যাগুলোর ডিভাইজার বিজোড় হয়। তাই উত্তর = floor(sqrt(n))।
বাইনারি সার্চ সমাধান
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)) # আউটপুট: 2সরল সমাধান
import math
def solve(n):
return int(math.isqrt(n)) # পাইথন ৩.৮+
# অথবা
def solve(n):
return int(n ** 0.5)সময় জটিলতা
O(log n) বাইনারি সার্চের জন্য, O(1) ম্যাথ ফাংশনের জন্য।
