020 — LCM using GCD¶

018-এ Euclid দিয়ে GCD শিখেছ — এবার তার সবচেয়ে সহজ আর সবচেয়ে কাজের আত্মীয়: LCM। মজার ব্যাপার, LCM আলাদা করে কষ্ট করে বের করতে হয় না — GCD জানা থাকলে এক লাইনেই হয়ে যায়। ধীরে পড়ো, gcd × lcm = a × b সূত্রটা কেন কাজ করে সেটা গেঁথে নাও।

Source¶

Original source: Classic exercise (related: Project Euler 5 — Smallest multiple)
Platform: Project Euler — https://projecteuler.net/problem=5
Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
Difficulty: Easy
Pattern: lcm = a // gcd(a, b) * b
Basic idea inherited from: 018 — GCD using Euclidean Algorithm

1. Problem in simple words¶

দুটো ধনাত্মক integer a আর b দেওয়া আছে। বের করতে হবে এদের LCM — least common multiple (লসাগু, লঘিষ্ঠ সাধারণ গুণিতক)। মানে এমন সবচেয়ে ছোট ধনাত্মক সংখ্যা যেটা a-রও multiple, b-রও।

উদাহরণ: lcm(12, 18) = 36, কারণ 36 = 12×3 আর 36 = 18×2 — দুজনেরই গুণিতক, আর এর চেয়ে ছোট কোনো সংখ্যা দুজনেরই গুণিতক নয়।

দৈনন্দিন কাজে এটা বারবার লাগে: দুটো ঘটনা যদি আলাদা আলাদা সময় পরপর ঘটে, তারা আবার একসাথে কখন ঘটবে — সেটাই LCM।

2. What is the math idea?¶

মূল সূত্র একটাই, আর সেটা GCD-র সাথে জড়ানো:

gcd(a, b) × lcm(a, b) = a × b

মানে lcm(a, b) = (a × b) / gcd(a, b)। যেহেতু GCD আমরা Euclid দিয়ে O(log) সময়ে বের করতে পারি, LCM-ও সেই একই সময়ে বেরিয়ে যায়।

কেন এই সূত্র? Factorization দিয়ে ভাবলে পরিষ্কার: প্রতিটা prime-এর জন্য GCD নেয় min power, LCM নেয় max power। আর যেকোনো দুই সংখ্যার জন্য min + max = দুজনের যোগফল — তাই gcd × lcm-এ প্রতিটা prime-এর power মিলে যায় ঠিক a × b-র সমান।

3. Which basic idea does this inherit from?¶

এটা সরাসরি 018 (GCD using Euclidean Algorithm)-এর উপর দাঁড়িয়ে। LCM-এর পুরো হিসাবটাই GCD-র উপর ভর করে — lcm = a // gcd(a, b) * b। GCD না জানলে LCM বের করা অনেক কঠিন (সব multiple ঘুরে দেখতে হতো)।

তাই LCM-এ আটকে গেলে এক ধাপ পিছিয়ে 018-এ যাও — gcd function ঠিকঠাক থাকলে LCM প্রায় বিনা পরিশ্রমে চলে আসে। এটাও মনে রাখার মতো: ভালো একটা building block (এখানে gcd) থাকলে তার উপরে নতুন জিনিস বানানো কত সহজ হয়।

4. Real-life analogy¶

ভাবো দুটো বাস স্টপ থেকে ছাড়ে — একটা প্রতি 12 মিনিটে, আরেকটা প্রতি 18 মিনিটে। দুটো বাসই যদি এইমাত্র একসাথে ছেড়ে থাকে, তাহলে আবার ঠিক একসাথে কখন ছাড়বে?

প্রথম বাস ছাড়ে 12, 24, 36, 48... মিনিটে। দ্বিতীয়টা 18, 36, 54... মিনিটে। প্রথম যে সময়ে দুটোই মেলে — 36 মিনিট। এটাই lcm(12, 18)।

খেয়াল করো — তুমি 36 খুঁজতে দুটো তালিকা মেলাতে পারতে, কিন্তু সেটা ধীর। GCD জানলে শর্টকাট: 12 × 18 / gcd(12,18) = 216 / 6 = 36। দুই বাস কখন আবার মিলবে — এক ভাগেই উত্তর।

5. Visual explanation¶

প্রথমে দুই সংখ্যার multiple-এর তালিকা মেলাও — প্রথম মিল কোথায়:

12-এর multiple : 12  24  36  48  60 ...
18-এর multiple : 18  36  54  72 ...
                      ^^
              প্রথম common = 36 = lcm(12, 18)

এবার সূত্রটা কেন কাজ করে, factorization দিয়ে দেখো (min/max power):

12 = 2^2 · 3^1
18 = 2^1 · 3^2

gcd = প্রতি prime-এর min power = 2^1 · 3^1 = 6
lcm = প্রতি prime-এর max power = 2^2 · 3^2 = 36

যাচাই: gcd × lcm = 6 × 36 = 216 = 12 × 18  ✓
তাই lcm = 12 × 18 / 6 = 36

6. Example input and output¶

   a  ,   b   ->  lcm
----------------------
  12  ,  18   ->  36
  4   ,   6   ->  12
  5   ,   7   ->  35      (coprime: lcm = a × b)
  6   ,  12   ->  12      (একজন অন্যজনের multiple)
  10  ,  10   ->  10      (একই সংখ্যা)
  7   ,   1   ->  7       (1-এর সাথে lcm = অন্য সংখ্যাটাই)

দুটো জিনিস খেয়াল করো: a, b coprime হলে (gcd = 1) lcm ঠিক a × b (যেমন 5, 7 → 35)। আর একজন অন্যজনের multiple হলে lcm হলো বড় সংখ্যাটাই (6, 12 → 12)।

7. Brute force thinking¶

GCD-সূত্র মাথায় না এলে, সবচেয়ে সরল চিন্তা — বড় সংখ্যাটার multiple একটা একটা করে বানাও, আর প্রথম যেটা ছোট সংখ্যাটা দিয়েও ভাগ যায়, সেটাই LCM:

def lcm_brute(a, b):
    if a == 0 or b == 0:
        return 0
    bigger = max(a, b)
    smaller = min(a, b)
    multiple = bigger
    while multiple % smaller != 0:    # দুজনেরই multiple হলো কি?
        multiple += bigger
    return multiple

এটা bigger-এর multiple একে একে দেখে (bigger, 2×bigger, ...), আর প্রথম যেটা smaller দিয়েও ভাগ যায় সেটাই উত্তর। বড় সংখ্যা থেকে শুরু করায় ছোট দিকটা দ্রুত মেলে। ঠিক উত্তর দেয়।

8. Why brute force may be slow¶

সমস্যা হলো এই loop সবচেয়ে খারাপ ক্ষেত্রে smaller বার পর্যন্ত ঘুরতে পারে। coprime সংখ্যায় (যেমন a = 999999937, b = 999999931, দুটো বড় prime) lcm = a × b, মানে loop প্রায় smaller সংখ্যক বার চলবে।

a, b দুটো ~10^9 আর coprime হলে:
  brute force : ~10^9 বার loop   (ধীর, O(min(a, b)))
  gcd-সূত্র   : ~30 ধাপ (gcd) + ১টা ভাগ-গুণ  (O(log min(a, b)))

মূল কথা: multiple একে একে খোঁজা অপচয়, যখন একটামাত্র সূত্রে সরাসরি উত্তর পাওয়া যায়। সেই সূত্রের চাবি হলো GCD।

9. Better thinking¶

মূল insight — LCM আর GCD পরস্পরের পরিপূরক: gcd × lcm = a × b। তাই GCD জানলেই LCM এক ভাগে বেরোয়।

GCD আমরা 018-এ Euclid দিয়ে O(log) সময়ে বের করতে শিখেছি। তাই:

def lcm(a, b):
    return a // gcd(a, b) * b

একটাই সূক্ষ্ম কৌশল — আগে ভাগ, পরে গুণ। a // gcd(a, b) সবসময় পূর্ণসংখ্যা (কারণ gcd নিশ্চিতভাবে a-কে ভাগ করে), তাই আগে ভাগ করলে কোনো ভগ্নাংশের ঝামেলা নেই, আর মাঝপথে অযথা বিশাল সংখ্যা (a × b) তৈরি হয় না।

10. Thinking tweak¶

আসল "আহা!" মুহূর্ত: LCM আলাদা করে খুঁজতে হয় না — GCD-র সাথে এর একটা সরল সম্পর্ক আছে, তাই একটা জানলেই অন্যটা free।

আর ছোট্ট practical মোচড়: a * b // gcd না লিখে a // gcd * b লেখো। দুটো একই উত্তর দেয়, কিন্তু প্রথমটায় a * b মাঝপথে বিশাল হয়ে overflow ঝুঁকি বাড়ায় (অন্য ভাষায়), আর Python-এ অযথা বড় সংখ্যা নিয়ে কাজ করে। "আগে ভাগ" — এই এক শব্দের অভ্যাসটা মনে রাখো।

11. Step-by-step dry run¶

চলো lcm(12, 18) ধীরে চালাই। আগে gcd, তারপর সূত্র:

ধাপ ১ — gcd(12, 18) বের করি (Euclid):

step	a	b	a % b
1	12	18	12
2	18	12	6
3	12	6	0 → থামো, gcd = 6

ধাপ ২ — সূত্র বসাই (আগে ভাগ, পরে গুণ):

lcm = a // gcd * b
    = 12 // 6 * 18
    = 2 * 18
    = 36

যাচাই: 36 = 12×3 = 18×2 — দুজনেরই multiple, আর এর ছোট কোনো common multiple নেই। lcm = 36, বাস-স্টপের গল্পের সাথে হুবহু মিলল।

12. Python solution¶

def gcd(a, b):
    """018-এর Euclid — LCM-এর ভিত্তি।"""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """a আর b-এর least common multiple, GCD দিয়ে।"""
    if a == 0 or b == 0:
        return 0                  # 0-এর সাথে common multiple ধরা হয় 0
    return abs(a) // gcd(a, b) * abs(b)   # আগে ভাগ, পরে গুণ


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert lcm(12, 18) == 36
assert lcm(4, 6) == 12
assert lcm(5, 7) == 35           # coprime -> a × b
assert lcm(6, 12) == 12          # একজন অন্যজনের multiple
assert lcm(10, 10) == 10         # একই সংখ্যা
assert lcm(7, 1) == 7            # 1-এর সাথে -> অন্য সংখ্যাটাই
assert lcm(18, 12) == 36         # ক্রম উল্টে দিলেও একই
assert lcm(0, 5) == 0            # edge case: 0
assert lcm(21, 6) == 42          # gcd 3 -> 21//3*6 = 42

print(lcm(12, 18))   # 36
print(lcm(5, 7))     # 35
print(lcm(6, 12))    # 12
print("সব test pass!")

13. Line-by-line explanation¶

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

এটা 018-এর সেই Euclid — LCM-এর ভিত্তি। বড় জোড়াকে ছোট জোড়ায় নামিয়ে নামিয়ে b = 0 হলে a-ই gcd।

    if a == 0 or b == 0:
        return 0

Edge case: 0-এর সাথে LCM আমরা 0 ধরি (0 যেকোনো সংখ্যার multiple, তাই "সবচেয়ে ছোট common multiple" 0)। এটা আলাদা করে না সামলালে নিচের সূত্রে gcd(0, b) = b দিয়ে ভাগ ঠিক চললেও 0 বেরোত — তবু পরিষ্কার রাখতে আগেই ধরছি।

    return abs(a) // gcd(a, b) * abs(b)

এটাই হৃদয়। প্রথমে a // gcd (নিশ্চিতভাবে পূর্ণসংখ্যা), তারপর * b। abs নিচ্ছি যাতে negative input এলেও LCM ধনাত্মক বেরোয়। "আগে ভাগ" — অযথা বিশাল মধ্যবর্তী সংখ্যা এড়াতে।

বাকি assert লাইনগুলো নিজেদের চেক করছে; সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough¶

চালালে যা ছাপবে:

36
35
12
সব test pass!

প্রথম তিন লাইন তিনটা print(lcm(...)) থেকে: (12,18) → 36, (5,7) → 35 (coprime, তাই a×b), (6,12) → 12 (12 হলো 6-এর multiple)। তার আগের সব assert চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity¶

O(log min(a, b)) — পুরো খরচটাই gcd বের করায় (Euclid, O(log))। তারপর একটা ভাগ আর একটা গুণ — constant কাজ। তাই 018-এর GCD যত দ্রুত, LCM-ও ঠিক তত দ্রুত। brute force-এর O(min(a, b))-এর তুলনায় বিশাল উন্নতি।

16. Space complexity¶

O(1) — gcd iterative হওয়ায় শুধু গুটিকয় variable লাগে, কোনো বাড়তি list বা array নেই। input ছাড়া আলাদা জায়গা প্রায় শূন্য।

17. Common mistakes¶

a * b // gcd লেখা — উত্তর ঠিক হলেও মাঝপথে a * b বিশাল হয়ে যায় (অন্য ভাষায় overflow)। সবসময় a // gcd * b — আগে ভাগ।
0-এর edge case ভুলে যাওয়া — lcm(0, x) সামলাতে ভুললে gcd(0, 0)-এ ভাগ করতে গিয়ে সমস্যা হতে পারে; তাই আগেই 0 ধরা ভালো।
negative ভুলে যাওয়া — LCM সবসময় ধনাত্মক ধরা হয়; abs না নিলে negative input-এ ঋণাত্মক উত্তর আসতে পারে।
নিজে নিজে multiple খোঁজা — GCD-সূত্র জানা থাকতে multiple loop চালানো অপচয়; সূত্রটাই মনে রাখো।
LCM আর GCD উল্টে ফেলা — GCD সবসময় ≤ min(a, b) (ছোট), LCM সবসময় ≥ max(a, b) (বড়)। উত্তর দেখে যাচাই করো ঠিক দিকেরটা পেয়েছ কি না।

18. Harder problems that inherit this idea¶

Project Euler 5 — Smallest multiple (https://projecteuler.net/problem=5) — 1 থেকে 20 পর্যন্ত সব সংখ্যার LCM; বারবার lcm প্রয়োগের সরাসরি অনুশীলন।
LeetCode — Ugly Number II (https://leetcode.com/problems/ugly-number-ii/) — multiple/factor চিন্তা গভীরে নেয়; common interview pattern।
022 (Count Coprime Pairs) আর 023 (Euler Phi Basic) — এই repo-রই পরের ধাপ, যেখানে gcd-ভিত্তিক চিন্তা আরও এগোয়।

19. Pattern learned¶

LCM via GCD — lcm(a, b) = a // gcd(a, b) * b, ভিত্তিতে gcd × lcm = a × b। মূল শিক্ষা: একটা ভালো building block (gcd) থাকলে তার উপরে নতুন উত্তর প্রায় বিনা খরচে গড়া যায়; আর সবসময় "আগে ভাগ, পরে গুণ"।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "LCM = a // gcd(a, b) * b (আগে ভাগ!); ভিত্তি gcd × lcm = a × b। দুটো সংখ্যা আবার কখন মিলবে / common multiple দরকার দেখলেই এটা মনে করব — GCD জানলে এক লাইনেই হয়।"

পরের ধাপ → 021 — Coprime Check (gcd = 1 হলে কী হয়)। শিকড় → 018 — GCD using Euclidean Algorithm।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)¶

JS-এ integer division নেই, তাই "আগে ভাগ, পরে গুণ"-এর ভাগটা Math.floor দিয়ে করি (gcd নিশ্চিতভাবে ভাগ করে, তাই floor নিরাপদ)।

// 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);
  while (b) [a, b] = [b, a % b];
  return a;
}

function lcm(a, b) {
  if (a === 0 || b === 0) return 0;               // 0-এর সাথে lcm = 0
  return Math.floor(Math.abs(a) / gcd(a, b)) * Math.abs(b);  // আগে ভাগ, পরে গুণ
}

// ---- test cases (file-এর example + edge case) ----
assert(lcm(12, 18) === 36, "12,18");
assert(lcm(4, 6) === 12, "4,6");
assert(lcm(5, 7) === 35, "coprime → a*b");
assert(lcm(6, 12) === 12, "multiple");
assert(lcm(10, 10) === 10, "same");
assert(lcm(7, 1) === 7, "with 1");
assert(lcm(18, 12) === 36, "ক্রম উল্টানো");
assert(lcm(0, 5) === 0, "edge 0");
assert(lcm(21, 6) === 42, "gcd 3");
console.log("সব JS test pass!");

JS টীকা: a * b / gcd না লিখে Math.floor(a / gcd) * b লেখো — JS number 2^53-এর বেশি integer ঠিক রাখে না, তাই মাঝপথে a*b বিশাল হলে নির্ভুলতা হারায়; "আগে ভাগ" সেটা এড়ায়। সত্যিই বড় সংখ্যায় BigInt দরকার।

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 lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.floor(Math.abs(a) / gcd(a, b)) * Math.abs(b);
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number, number, number]> = [
  [12, 18, 36], [4, 6, 12], [5, 7, 35], [6, 12, 12],
  [10, 10, 10], [7, 1, 7], [0, 5, 0], [21, 6, 42],
];
for (const [a, b, want] of cases) expect(lcm(a, b), want, `lcm(${a},${b})`);
console.log("সব TS test pass!");

TS টীকা: return type number আর tuple [number, number, number] থাকায় test table-এর প্রতিটা সারি গঠনে ভুল থাকলে compile-time-এ ধরা পড়ে — boundary গণনার ভুল আগেই আটকায়।

23. কোথায় কাজে লাগে (real-world use)¶

Periodic event alignment: দুটো cron job / signal / blinking light আলাদা interval-এ চললে আবার কখন একসাথে — lcm(period1, period2)।
Fraction addition: ভিন্ন হরের ভগ্নাংশ যোগ করতে common denominator = হরগুলোর LCM।
Gear / rotation / animation cycles: দুই চাকা বা animation loop কত পরে আবার একই অবস্থানে ফেরে।
Buffer / chunk sizing: দুই system আলাদা block size-এ কাজ করলে সবচেয়ে ছোট মিল-আকার = LCM। মূল pattern — "একটা ভালো building block (gcd) থাকলে নতুন উত্তর প্রায় বিনা খরচে; gcd × lcm = a × b" — composition আর reuse-এর চিন্তায় বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।