পাইথনে দুটি সংখ্যার শিফটেড টেবিলের মধ্যবর্তী ন্যূনতম পার্থক্য

দুটি সংখ্যা p এবং q দেওয়া আছে। তাদের অসীম গুণন টেবিল (multiplication table) আছে। এই টেবিলগুলো r এবং s পরিমাণ শিফট (shift) করা হয়েছে (r, s ≥ 0)। শিফটেড টেবিলের যেকোনো দুটি पदের মধ্যে ন্যূনতম পার্থক্য বের করতে হবে।

উদাহরণ

ইনপুট: p = 7, q = 17, r = 6, s = 3

টেবিল ৭: [7, 14, 21, 28, 35, 42, 49, ...] → শিফটেড: [13, 20, 27, 34, 41, 48, 55, ...]

টেবিল ১৭: [17, 34, 51, 68, 85, 102, 119, ...] → শিফটেড: [20, 37, 54, 71, 88, 105, 121, ...]

ন্যূনতম পার্থক্য = 20 - 20 = ০

আউটপুট: ০

সমাধানের পদ্ধতি

g = gcd(p, q) বের করুন।
difference = |r - s| % g হিসাব করুন।
উত্তর = min(difference, g - difference)

এই ফর্মুলা মডুলার αριথমেটিক (modular arithmetic) ও চাইনিজ রিমেইন্ডার থিওরেম (Chinese Remainder Theorem) এর ওপর ভিত্তি করে কাজ করে।

পাইথন কোড

import math

def get_minimum_diff(p, q, r, s):
    g = math.gcd(p, q)
    difference = abs(r - s) % g
    return min(difference, g - difference)

p = 7
q = 17
r = 6
s = 3
print(get_minimum_diff(p, q, r, s))

ইনপুট

7, 17, 6, 3