কনটেন্টে যান

020 — LCM using GCD

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

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

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

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

Input ও 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)।

চেনা উদাহরণে বোঝা

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

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

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

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

ভেতরের অঙ্ক

মূল সূত্র একটাই, আর সেটা 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-র সমান।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

Python
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 দিয়েও ভাগ যায় সেটাই উত্তর। বড় সংখ্যা থেকে শুরু করায় ছোট দিকটা দ্রুত মেলে। ঠিক উত্তর দেয়।

কোথায় বেশি কাজ হতে পারে

সমস্যা হলো এই 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।

আরও ভালোভাবে ভাবা

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

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

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

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

ভাবনার পরিবর্তন

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

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

ছবিতে বোঝা

প্রথমে দুই সংখ্যার 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

ছোট input-এ ধাপে ধাপে

চলো 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, বাস-স্টপের গল্পের সাথে হুবহু মিলল।

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

উদাহরণ
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! ছাপে।

Output মিলিয়ে দেখা

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

উদাহরণ
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!।

JavaScript ও test cases

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

JavaScript
// 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 দরকার।

TypeScript ও test cases

TypeScript
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 গণনার ভুল আগেই আটকায়।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

  • 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-ভিত্তিক চিন্তা আরও এগোয়।

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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।

কোথায় কাজে লাগে

  • 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" লেখা হয়েছে।