সমস্যা বিবরণ
দুটি সংখ্যা A এবং B দেওয়া আছে। প্রতিটি অপারেশনে যেকোনো একটি সংখ্যাকে ১ বাড়াতে বা কমাতে পারেন। gcd(A, B) ≠ 1 (নন-কোপরাইম) করার ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।
উদাহরণ
Input: A = 8, B = 9
Output: 1
ব্যাখ্যা: 9 → 10 করলে gcd(8, 10) = 2 ≠ 1
গাণিতিক অভিজ্ঞতা
- যদি
gcd(A, B) ≠ 1ইতিমধ্যে → ০ অপারেশন - যদি যেকোনো একটি ইভেন (জোড়) হয় → ১ অপারেশন (অন্যটি ইভেন করলে gcd ≥ 2)
- উভয় ওড্ড (বিজোড়) হলে:
- একটি ±1 করলে ইভেন হয় → gcd ≥ 2 (১ অপারেশন)
- এক্সেপশন: উভয়ই প্রাইম এবং টুইন প্রাইম (যেমন 3,5 বা 5,7) হলে ±1 করলেও কোপরাইম থাকতে পারে → ২ অপারেশন
পাইথন কোড
from math import gcd
class Solution:
def solve(self, a, b):
# ইতিমধ্যে নন-কোপরাইম
if gcd(a, b) != 1:
return 0
# যেকোনো একটি ইভেন
if a % 2 == 0 or b % 2 == 0:
return 1
# উভয় ওড্ড: ±1 চেক করুন
if (gcd(a + 1, b) != 1 or
gcd(a - 1, b) != 1 or
gcd(a, b - 1) != 1 or
gcd(a, b + 1) != 1):
return 1
return 2
ob = Solution()
print(ob.solve(8, 9)) # 1
print(ob.solve(3, 5)) # 2 (Twin primes: 3→4 gcd(4,5)=1, 5→6 gcd(3,6)=3! wait...)
# Actually for 3,5: 5→6 makes gcd(3,6)=3, so answer is 1
print(ob.solve(7, 11)) # 2? Let's check: 7→8 gcd(8,11)=1, 11→10 gcd(7,10)=1... need 2 ops
কোরেকশন: ৩,৫ কেস
a=3, b=5 (both odd, gcd=1)
a+1=4, gcd(4,5)=1
a-1=2, gcd(2,5)=1
b-1=4, gcd(3,4)=1
b+1=6, gcd(3,6)=3 ≠ 1 ← এইটা True!
So answer = 1
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(log min(a,b)) — GCD কমপ্লেক্সিটি
- স্থান জটিলতা: O(1)
উপসংহার
- অপারেশন ০, ১, বা ২ এর বাইরে কখনো হয় না
- গাণিতিক প্রমাণ: সবসময় ≤ ২ অপারেশনই লাগে
- Edge case: (1, 1) → gcd=1, but 1 is odd... 1+1=2, gcd(2,1)=1, need 2 ops? Actually gcd(1,1)=1, 1→2 makes gcd(2,1)=1, 1→0 invalid. Special case.
