018 — GCD using Euclidean Algorithm¶
এই note থেকে আমরা এই level-এর সবচেয়ে শক্তিশালী tool-গুলোর একটা শিখব — Euclid-এর GCD। ২৩০০ বছরের পুরোনো এই কৌশল এত সুন্দর যে একবার বুঝলে সারাজীবন মনে থাকবে। ধীরে পড়ো, tile-এর ছবিটা চোখে আঁকো — তাহলেই "কেন কাজ করে" গেঁথে যাবে।
Source¶
- Original source: CP-Algorithms — Euclidean algorithm for GCD
- Platform: CP-Algorithms — https://cp-algorithms.com/algebra/euclid-algorithm.html
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Easy
- Pattern: Euclid — gcd(a, b) = gcd(b, a % b)
- Basic idea inherited from: — (এটা নতুন শিকড়; তবে divisibility/remainder চিন্তা 011-এর হাত ধরে এসেছে)
1. Problem in simple words¶
দুটো ধনাত্মক integer a আর b দেওয়া আছে। বের করতে হবে এদের GCD — greatest common divisor (গরিষ্ঠ সাধারণ গুণনীয়ক)। মানে এমন সবচেয়ে বড় সংখ্যা যেটা a-কেও নিঃশেষে ভাগ করে, b-কেও।
একটা উদাহরণ: gcd(48, 18) = 6, কারণ 6 দিয়ে 48-ও ভাগ যায় (48 = 6×8), 18-ও যায় (18 = 6×3), আর 6-এর চেয়ে বড় কোনো সংখ্যা দুটোকেই একসাথে ভাগ করতে পারে না।
দেখতে সরল, কিন্তু এটাই LCM, coprime, modular inverse — সবকিছুর ভিত্তি। তাই এই একটা জিনিস ঝটপট, bug ছাড়া লিখতে পারাটা পুরো level-এর চাবিকাঠি।
2. What is the math idea?¶
মূল idea একটাই, আর সেটা Euclid-এর: gcd(a, b) = gcd(b, a % b)।
মানে বড় জোড়াটাকে বারবার ছোট জোড়ায় নামাতে থাকো — (a, b) থেকে (b, a % b)-তে। প্রতিবার দ্বিতীয় সংখ্যাটা কমে আসে, একসময় 0 হয়ে যায়। যখন b = 0, তখন উত্তর হলো সেই মুহূর্তের a। কারণ gcd(a, 0) = a — যেকোনো সংখ্যা 0-কে ভাগ করে, তাই a-ই সবচেয়ে বড় common divisor।
এর পেছনের core concept হলো remainder আর divisibility — সেই % operator, যেটা 001 থেকে আমাদের সাথে আছে।
3. Which basic idea does this inherit from?¶
এটা এই level-এ একটা নতুন শিকড় (তাই "inherited from: —"), কিন্তু পুরো শূন্য থেকে নয়। এর তলায় আছে দুটো চেনা জিনিস:
- 011 (Divisibility Rules) / remainder — "b কি a-কে নিঃশেষে ভাগ করে?" এই প্রশ্নটাই GCD-র মূল।
a % bদিয়ে আমরা সেই বাকি অংশ মাপি। - Common divisor-এর ধারণা — দুটো সংখ্যার সাধারণ গুণনীয়ক খোঁজা।
আর উল্টোদিকে, এই problem নিজে অনেক কিছুর শিকড়: 019 (Extended GCD), 020 (LCM), 021 (Coprime) — সবাই এই gcd function-এর উপর দাঁড়াবে।
4. Real-life analogy¶
ভাবো তোমার একটা মেঝে আছে 48 × 18 মাপের, আর তুমি চাও সবচেয়ে বড় square tile দিয়ে পুরোটা ঢাকতে — যাতে একটাও tile কাটতে না হয়।
প্রথমে যত বড় square পারো বসাও — 18 × 18। দুটো বসে গেল (18 + 18 = 36), বাকি রইল 48 − 36 = 12 চওড়া একটা ফালি। এখন সেই 18 × 12 ফালিতে একই প্রশ্ন: সবচেয়ে বড় square কী? 12 × 12 বসাও, বাকি 12 × 6। আবার: 6 × 6 বসাও — পুরোপুরি মিলে গেল, কিছু বাকি নেই।
সেই শেষ square-এর মাপ 6 — এটাই gcd(48, 18)। প্রতিবার "বাকি ফালি" নিয়ে ছোট সমস্যায় নামা — এটাই Euclid-এর জাদু।
5. Visual explanation¶
প্রথমে tile-এর সেই গল্পটা ছবিতে দেখো:
48 × 18 মেঝে, সবচেয়ে বড় square tile খুঁজছি:
+----------+----------+------+
| | | |
| 18 × 18 | 18 × 18 | 18×12| <- বাকি ফালি = নতুন সমস্যা
| | | |
+----------+----------+------+
48 % 18 = 12
ধাপে ধাপে জোড়া ছোট হয়:
(48, 18) -> (18, 12) -> (12, 6) -> (6, 0) -> উত্তর 6
এবার number/remainder-এর ছবিতে দেখো — দ্বিতীয় সংখ্যাটা কীভাবে দ্রুত 0-র দিকে নামে:
step : a b a % b
-------------------------------
1 : 48 , 18 -> 12
2 : 18 , 12 -> 6
3 : 12 , 6 -> 0
4 : 6 , 0 -> থামো! উত্তর = a = 6
লক্ষ করো — প্রতি ধাপে b ছোট হচ্ছে, আর একসময় 0 হলেই খেলা শেষ। ঠিক সেই মুহূর্তের a-ই উত্তর।
6. Example input and output¶
a , b -> gcd
------------------------
48 , 18 -> 6
18 , 48 -> 6 (উল্টে দিলেও একই উত্তর)
17 , 5 -> 1 (coprime — কোনো common factor নেই)
100 , 10 -> 10 (একজন অন্যজনের multiple)
7 , 0 -> 7 (gcd(a, 0) = a)
0 , 0 -> 0 (edge case: দুটোই 0)
12 , 12 -> 12 (একই সংখ্যা)
খেয়াল করো: gcd(a, 0) = a — এটাই algorithm থামার শর্ত। আর gcd(0, 0) কে আমরা 0 ধরি (যদিও গাণিতিকভাবে অসংজ্ঞায়িত, code-এ এটাই স্বাভাবিকভাবে বেরোয়)।
7. Brute force thinking¶
Euclid মাথায় না এলে প্রথমে যেটা আসে — দুটো সংখ্যার মধ্যে যেটা ছোট, তার থেকে 1 পর্যন্ত নিচে নেমে প্রথম যে সংখ্যা দুটোকেই ভাগ করে, সেটাই GCD:
def gcd_brute(a, b):
a, b = abs(a), abs(b)
if a == 0 or b == 0:
return a or b # একটা 0 হলে অন্যটাই উত্তর
for d in range(min(a, b), 0, -1):
if a % d == 0 and b % d == 0:
return d
এটা min(a, b) থেকে শুরু করে নিচে নামে, আর প্রথম যে সংখ্যা দুটোকেই ভাগ করে সেটাই সবচেয়ে বড় common divisor — তাই উত্তর ঠিক। সরল, বোঝা সহজ।
8. Why brute force may be slow¶
সমস্যা হলো এই loop সবচেয়ে খারাপ ক্ষেত্রে min(a, b) বার ঘোরে। যেমন gcd(1, 1000000000) — loop ঠিক 1 বারেই থামবে (ভাগ্য ভালো), কিন্তু gcd(999999937, 999999937) মানে দুটো বড় prime-এর মতো সংখ্যা হলে loop প্রায় পুরোটা নামতে হবে।
a = b = 1000000000 হলে:
brute force: ~10^9 বার loop (ধীর, O(min(a, b)))
Euclid : ~30 ধাপের কম (চোখের নিমেষে, O(log min(a, b)))
মূল কথা: একটা একটা করে নিচে নামা অপচয়, যখন আমরা প্রতি ধাপে সংখ্যাটাকে অর্ধেকেরও বেশি ছোট করতে পারি। সেই বড় লাফটাই Euclid দেয়।
9. Better thinking¶
মূল insight — যে সংখ্যা a আর b দুটোকেই ভাগ করে, সে a % b-কেও ভাগ করে।
কেন? a = b × q + r (এখানে r = a % b)। যদি কোনো সংখ্যা d দুটো a আর b-কে ভাগ করে, তাহলে r = a − b × q-কেও সে ভাগ করবে (কারণ ডানপাশের দুই অংশই d দিয়ে ভাগ যায়)। উল্টোটাও সত্যি। মানে (a, b)-এর common divisor-দের তালিকা আর (b, r)-এর তালিকা হুবহু একই।
তালিকা একই হলে তার সবচেয়ে বড়টাও একই — তাই gcd(a, b) = gcd(b, a % b)। প্রতি ধাপে আমরা বড় সংখ্যাটা ফেলে দিয়ে ছোট remainder নিয়ে কাজ করি, আর b = 0 হলেই উত্তর হাতে।
10. Thinking tweak¶
আসল "আহা!" মুহূর্ত: GCD খুঁজতে প্রতিটা সম্ভাব্য divisor চেক করার দরকার নেই — শুধু বড় সংখ্যাটাকে ছোট সংখ্যা দিয়ে ভাগ করে remainder নিলেই সমস্যা ছোট হয়ে যায়।
বিয়োগের ভাষায় ভাবলে আরও পরিষ্কার: gcd(a, b) = gcd(a − b, b) — বড়টা থেকে ছোটটা বিয়োগ করলেও GCD বদলায় না। % আসলে সেই বিয়োগটাই একসাথে অনেকবার করে দেয় (48 থেকে 18 দুবার বিয়োগ = 48 % 18)। এই "বিয়োগ বারবার = modulo" tweak-টাই brute force-কে log-এ নামিয়ে আনে।
11. Step-by-step dry run¶
চলো gcd(48, 18) ধীরে চালাই। iterative version-এ প্রতি ধাপে a, b = b, a % b হয়:
| step | a (শুরুতে) | b (শুরুতে) | a % b | নতুন (a, b) |
|---|---|---|---|---|
| 1 | 48 | 18 | 12 | (18, 12) |
| 2 | 18 | 12 | 6 | (12, 6) |
| 3 | 12 | 6 | 0 | (6, 0) |
| 4 | 6 | 0 | — | b = 0, loop থামল |
শেষে b = 0, তাই উত্তর হলো a = 6। মিলিয়ে দেখো: 48 = 6×8, 18 = 6×3 — দুটোই 6 দিয়ে ভাগ যায়, আর এর বড় কেউ পারে না। gcd = 6।
tile-এর গল্পের ঠিক সেই চারটে ধাপ — একই সত্য, এবার সংখ্যায়।
12. Python solution¶
def gcd(a, b):
"""a আর b-এর greatest common divisor (iterative Euclid)।"""
a, b = abs(a), abs(b) # negative হলেও GCD ধনাত্মক
while b:
a, b = b, a % b # বড় জোড়াকে ছোট জোড়ায় নামাই
return a
def gcd_recursive(a, b):
"""একই Euclid, কিন্তু recursion দিয়ে — সংজ্ঞাটা হুবহু ফুটে ওঠে।"""
a, b = abs(a), abs(b)
if b == 0:
return a
return gcd_recursive(b, a % b)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert gcd(48, 18) == 6
assert gcd(18, 48) == 6 # ক্রম উল্টে দিলেও একই
assert gcd(17, 5) == 1 # coprime
assert gcd(100, 10) == 10 # একজন অন্যজনের multiple
assert gcd(7, 0) == 7 # gcd(a, 0) = a
assert gcd(0, 0) == 0 # edge case
assert gcd(12, 12) == 12 # একই সংখ্যা
assert gcd(-48, 18) == 6 # negative-ও সামলায়
assert gcd_recursive(48, 18) == 6
assert gcd_recursive(270, 192) == 6
print(gcd(48, 18)) # 6
print(gcd(17, 5)) # 1
print(gcd(100, 10)) # 10
print("সব test pass!")
13. Line-by-line explanation¶
GCD সবসময় ধনাত্মক, তাই শুরুতেই দুটো সংখ্যার absolute value নিই — negative input এলেও যেন ঝামেলা না হয়।
এটাই হৃদয়। while b মানে "যতক্ষণ b শূন্য নয়" (Python-এ 0 হলো falsy)। প্রতি ঘোরে একসাথে দুটো কাজ: নতুন a হয় পুরোনো b, আর নতুন b হয় পুরোনো a % b। এই একসাথে assignment (tuple unpacking) জরুরি — না হলে a বদলে যাওয়ার পর ভুল b বের হতো।
Loop থামে যখন b = 0। তখন a-ই হলো GCD (কারণ gcd(a, 0) = a)।
gcd_recursive-এ একই কাজ, কিন্তু base case (b == 0 হলে a ফেরত) আর recursive call (gcd(b, a % b)) — Euclid-এর সংজ্ঞাটা যেন সরাসরি লেখা।
বাকি assert লাইনগুলো নিজেদের চেক করছে; সব ঠিক থাকলে শেষে সব test pass! ছাপে।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম তিন লাইন তিনটা print(gcd(...)) থেকে: (48,18) → 6, (17,5) → 1, (100,10) → 10। তার আগের সব assert চুপচাপ pass করেছে (assert fail করলেই কেবল চিৎকার করে থামত)। সবশেষে সব test pass! — মানে recursive version সহ সব ঠিক আছে।
15. Time complexity¶
O(log min(a, b)) — প্রতি দুই ধাপে বড় সংখ্যাটা অন্তত অর্ধেক হয়ে যায় (এটা গাণিতিকভাবে প্রমাণযোগ্য — সবচেয়ে খারাপ ক্ষেত্র হলো পরপর Fibonacci সংখ্যা)। তাই 10¹⁸ মাপের সংখ্যাতেও ৯০-এর কম ধাপে শেষ। brute force-এর O(min(a, b))-এর তুলনায় এটা আকাশ-পাতাল পার্থক্য।
16. Space complexity¶
O(1) iterative version-এ — শুধু a আর b, দুটো variable, আর কিছু লাগে না। recursive version-এ অবশ্য call stack-এ O(log min(a, b)) জায়গা লাগে (প্রতি call একটা frame), কিন্তু সেটাও খুবই ছোট।
17. Common mistakes¶
while bনা লিখেwhile b > 0লেখা — সাধারণত একই, কিন্তু abs না নিলে negative-এ গোলমাল হতে পারে। আমরা শুরুতেই abs নিচ্ছি বলে নিরাপদ।- Tuple assignment ভেঙে দুই লাইনে লেখা —
a = bতারপরb = a % bলিখলে দ্বিতীয় লাইনেaইতিমধ্যে বদলে গেছে, ভুল উত্তর। সবসময়a, b = b, a % bএকসাথে। - gcd(a, 0)-এর ক্ষেত্র ভুলে যাওয়া — মনে রেখো এটাই থামার শর্ত, error নয়; উত্তর
a। - 0 দিয়ে modulo-র ভয় — চিন্তা নেই, loop ঢোকার আগেই
b = 0হলে loop চলে না, তাইa % 0কখনো হয় না। - GCD আর LCM গুলিয়ে ফেলা — GCD হলো সবচেয়ে বড় common divisor (ছোট হয়), LCM সবচেয়ে ছোট common multiple (বড় হয়)।
18. Harder problems that inherit this idea¶
- CP-Algorithms — Extended Euclidean (https://cp-algorithms.com/algebra/extended-euclid-algorithm.html) — এই gcd-র ধাপগুলো উল্টে হেঁটে
a·x + b·y = gcdবের করা; আমাদের পরের problem 019। - LeetCode — Greatest Common Divisor of Strings (https://leetcode.com/problems/greatest-common-divisor-of-strings/) — সংখ্যার GCD-র যুক্তি string-এ প্রয়োগ; common interview pattern।
- 020 (LCM using GCD) আর 021 (Coprime Check) — এই repo-রই পরের ধাপ, যেখানে gcd সরাসরি কাজে লাগবে।
19. Pattern learned¶
Euclidean reduction — gcd(a, b) = gcd(b, a % b), আর gcd(a, 0) = a। বড় সমস্যাকে remainder দিয়ে দ্রুত ছোট সমস্যায় নামানো। এই "বিয়োগ/modulo দিয়ে জোড়া ছোট করা" pattern শুধু GCD নয়, পরে modular arithmetic-এও বারবার ফিরবে।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "GCD = while b: a, b = b, a % b; থামলে a-ই উত্তর। দুটো সংখ্যার common divisor খুঁজতে দেখলেই Euclid মনে করব — O(log)-এ শেষ, আর এটাই LCM/coprime/inverse সবকিছুর ভিত্তি।"
পরের ধাপ → 019 — Extended GCD Intro (এই ধাপগুলোই উল্টে হেঁটে x, y বের করব)। সম্পর্কিত → 020 — LCM using GCD, 021 — Coprime Check।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
21. JavaScript solution (with test cases)¶
JS-এ % negative-এ চিহ্ন রাখে (-48 % 18), তাই শুরুতেই Math.abs নিয়ে নিরাপদ থাকি।
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function gcd(a, b) {
a = Math.abs(a); b = Math.abs(b); // GCD ধনাত্মক
while (b) { // b !== 0 যতক্ষণ
[a, b] = [b, a % b]; // বড় জোড়াকে ছোট জোড়ায়
}
return a;
}
// recursion দিয়ে একই Euclid
function gcdRec(a, b) {
a = Math.abs(a); b = Math.abs(b);
return b === 0 ? a : gcdRec(b, a % b);
}
// ---- test cases (file-এর example + edge case) ----
assert(gcd(48, 18) === 6, "48,18");
assert(gcd(18, 48) === 6, "ক্রম উল্টানো");
assert(gcd(17, 5) === 1, "coprime");
assert(gcd(100, 10) === 10, "multiple");
assert(gcd(7, 0) === 7, "gcd(a,0)=a");
assert(gcd(0, 0) === 0, "edge 0,0");
assert(gcd(12, 12) === 12, "same");
assert(gcd(-48, 18) === 6, "negative");
assert(gcdRec(270, 192) === 6, "recursive");
console.log("সব JS test pass!");
JS টীকা: Python-এ
-48 % 18 == 6(সবসময় ≥ 0), কিন্তু JS-এ-48 % 18 === -6(চিহ্ন dividend-এর) — তাই শুরুতেইMath.abs(a), Math.abs(b)না নিলে negative input-এ ভুল হতে পারে।while (b)ঠিক কাজ করে কারণ 0 falsy।
22. TypeScript solution (with test cases)¶
function gcd(a: number, b: number): number {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) [a, b] = [b, a % b];
return a;
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray<readonly [number, number, number]> = [
[48, 18, 6], [18, 48, 6], [17, 5, 1], [100, 10, 10],
[7, 0, 7], [0, 0, 0], [12, 12, 12], [-48, 18, 6],
];
for (const [a, b, want] of cases) expect(gcd(a, b), want, `gcd(${a},${b})`);
console.log("সব TS test pass!");
TS টীকা:
[number, number, number]tuple টাইপ দিলে test table-এ ভুল arity (যেমন একটা সংখ্যা বাদ) compile-time-এই ধরা পড়ে — runtime crash নয়।
23. কোথায় কাজে লাগে (real-world use)¶
- Fraction simplify:
n/dকেgcd(n,d)দিয়ে ভাগ করে lowest terms — calculator, spreadsheet, symbolic math-এ নিত্য। - Aspect ratio / tiling: screen বা image-এর
w:hকে simplest ratio-তে নামানো (যেমন 1920×1080 → 16:9), বা বড় square tile দিয়ে গ্রিড ঢাকা। - Scheduling / cycle alignment: দুই periodic ঘটনা কখন মেলে তার ভিত্তি (LCM, যা gcd থেকে আসে)।
- Cryptography (modular inverse): extended Euclid দিয়ে
a·x + b·y = gcd— RSA key, modular inverse-এর core। মূল pattern — "বড় সমস্যাকে remainder দিয়ে দ্রুত ছোট সমস্যায় নামানো (O(log))" — modular arithmetic, number theory জুড়ে বড় ছবিতে ফেরে।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।