022 — Count Coprime Pairs Basic

021-এ শিখেছ দুটো সংখ্যা coprime কি না বলা। এবার এক ধাপ এগিয়ে — একটা তালিকার মধ্যে কতগুলো জোড়া coprime, সেটা গোনা। এটাই প্রথম problem যেখানে আমরা gcd-কে অনেকবার, জোড়ায় জোড়ায় চালাব। ধীরে পড়ো — pair গোনার সময় কোন জোড়া দুবার গুনছ না, সেই খেয়ালটাই আসল।

Source

• Original source: Classic exercise
• Platform: Classic exercise / — (judge-free)
• Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
• Difficulty: Medium
• Pattern: gcd over all pairs (i < j)
• Basic idea inherited from: 021 — Coprime Check

1. Problem in simple words

ধনাত্মক integer-এর একটা list দেওয়া আছে। বের করতে হবে — এর মধ্যে কতগুলো জোড়া (pair) পরস্পর coprime, মানে যাদের gcd ঠিক 1।

জোড়া বলতে আমরা বুঝি দুটো আলাদা position-এর সংখ্যা, আর (i, j) ও (j, i) একই জোড়া — তাই একবারই গুনব। সাজানোর ক্রম গুরুত্বপূর্ণ নয়।

উদাহরণ: list = [2, 3, 4] হলে সম্ভাব্য জোড়া তিনটে — (2,3), (2,4), (3,4)। এদের মধ্যে (2,3) coprime, (3,4) coprime, কিন্তু (2,4) coprime নয় (gcd 2)। তাই উত্তর 2।

2. What is the math idea?

মূল idea দুটো জিনিসের সংমিশ্রণ:

• coprime check = gcd(a, b) == 1 (021 থেকে)।
• সব জোড়া দেখা = list-এর প্রতিটা দুই-উপাদানের সমাবেশ (combination) একবার করে দেখা, মানে i < j ধরে দুটো nested loop।

মোট জোড়ার সংখ্যা n উপাদানের জন্য n × (n−1) / 2 (এটাই "n থেকে 2 বাছার" সংখ্যা — Level 3-এর combination-এর আগাম দর্শন)। প্রতিটা জোড়ায় gcd চালিয়ে 1 হলে count বাড়াই।

3. Which basic idea does this inherit from?

এটা সরাসরি 021 (Coprime Check)-এর উপর দাঁড়িয়ে। 021-এ আমরা একটা জোড়া coprime কি না বলতাম; এখানে সেই check-টাই সব জোড়ায় চালাই আর গুনি।

মূল নতুন জিনিস coprime-এ নয় — সেটা 021 থেকে ready। নতুন জিনিস হলো "সব জোড়া কীভাবে ঠিক একবার করে দেখব" — সেই i < j কৌশল। তাই coprime অংশে আটকালে 021-এ ফিরে যাও; pair গোনায় আটকালে নিচের visualization দেখো।

4. Real-life analogy

ভাবো একটা ঘরে কয়েকজন মানুষ আছে, আর তুমি জানতে চাও — কতগুলো জোড়া পরস্পর handshake করতে পারে। প্রত্যেকে প্রত্যেকের সাথে একবারই হাত মেলায়, আর "ক হাত মেলাল খ-র সাথে" আর "খ হাত মেলাল ক-র সাথে" — একই handshake, দুবার গোনা যাবে না।

আমাদের problem-এ সেই handshake-টা শর্তসাপেক্ষ: দুজন তখনই "মেলে" যখন তারা coprime (gcd 1)। তাই আমরা প্রতিটা সম্ভাব্য জোড়া একবার করে দেখি, আর শুধু coprime জোড়াগুলো গুনি। i < j শর্তটাই নিশ্চিত করে কোনো handshake দুবার গোনা হচ্ছে না।

5. Visual explanation

list = [2, 3, 4]-এর সব জোড়া একটা ত্রিভুজাকার ছকে (শুধু i < j):

        j=0(2)  j=1(3)  j=2(4)
i=0(2)    -      (2,3)   (2,4)
i=1(3)    -        -     (3,4)
i=2(4)    -        -       -

শুধু উপরের ত্রিভুজ (i < j) দেখি — নিচেরটা একই জোড়ার পুনরাবৃত্তি।

এবার প্রতিটা জোড়ায় gcd চালিয়ে সিদ্ধান্ত:

(2,3): gcd 1  -> coprime ✓   count = 1
(2,4): gcd 2  -> না        ✗   count = 1
(3,4): gcd 1  -> coprime ✓   count = 2

মোট coprime জোড়া = 2

6. Example input and output

   list              ->  coprime pairs
---------------------------------------
  [2, 3, 4]          ->  2     (2,3) আর (3,4)
  [1, 2, 3, 4]       ->  5     1 সবার সাথে coprime: (1,2)(1,3)(1,4) + (2,3)(3,4)
  [6, 10, 15]        ->  0     তিনজনেরই কোনো-না-কোনো common factor
  [5, 7, 11]         ->  3     তিনটেই prime -> সব জোড়া coprime
  [4]                ->  0     একটামাত্র উপাদান, কোনো জোড়া নেই
  []                 ->  0     খালি list
  [2, 2, 3]          ->  2     (2,3) দুবার (দুটো 2-ই 3-এর সাথে); (2,2) নয়

দুটো জিনিস খেয়াল করো: 1 সব কিছুর সাথে coprime, তাই list-এ 1 থাকলে সে প্রতিটা জোড়ায় coprime যোগ করে। আর [6,10,15] মজার — কোনো একটা সংখ্যা সবার সাথে common factor share করে না, কিন্তু প্রতিটা জোড়ায় কোনো-না-কোনো common factor আছে (6&10→2, 6&15→3, 10&15→5), তাই উত্তর 0।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — প্রতিটা সম্ভাব্য জোড়া ঘুরে gcd দেখি, 1 হলে গুনি। দুটো nested loop, বাইরেরটা i, ভেতরেরটা j = i+1 থেকে (যাতে i < j):

def count_coprime_pairs_brute(arr):
    from math import gcd
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(arr[i], arr[j]) == 1:
                count += 1
    return count

বাইরের loop প্রতিটা উপাদান ধরে, ভেতরের loop তার পরের সব উপাদানের সাথে জোড়া বানায় — তাই প্রতিটা জোড়া ঠিক একবার। gcd 1 হলে count বাড়ে। সরল, ঠিক উত্তর দেয়, আর এই level-এ এটাই গ্রহণযোগ্য সমাধান।

8. Why brute force may be slow

জোড়ার সংখ্যা n × (n−1) / 2 — মানে প্রায় O(n²) জোড়া, আর প্রতিটায় একটা gcd (O(log max))। তাই মোট খরচ O(n² · log max)।

n = 100   -> ~4,950 জোড়া      (চোখের নিমেষে)
n = 1,000 -> ~499,500 জোড়া     (এখনো ঠিক আছে)
n = 100,000 -> ~5×10^9 জোড়া   (অনেক ধীর — TLE)

ছোট-মাঝারি n-এ এই O(n²) ঠিক আছে (তাই Difficulty Medium, basic version)। কিন্তু n বিশাল হলে এটা ধীর — তখন Euler phi / Möbius-ভিত্তিক চালাকি লাগে (Level 2+)। এখন আমরা সচেতনভাবে সরল O(n²)-ই রাখছি, কারণ এটা বুঝতে সহজ আর correctness যাচাই করা যায়।

9. Better thinking

এই "basic" version-এর মূল লক্ষ্য দ্রুততা নয়, সঠিকতা আর পরিষ্কার pair-গোনা। তাই সবচেয়ে বড় insight এখানে algorithmic চমক নয়, বরং সতর্কতা:

• প্রতিটা জোড়া ঠিক একবার গোনো — j শুরু করো i + 1 থেকে, 0 থেকে নয়। তাহলে (i, j) আর (j, i) দুবার গোনা হবে না, আর কোনো উপাদান নিজের সাথে (i == j) জোড়া বাঁধবে না।
• gcd-কে রি-ইনভেন্ট কোরো না — 018-এর Euclid বা Python-এর math.gcd ব্যবহার করো।

def count_coprime_pairs(arr):
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):       # i < j: প্রতি জোড়া একবার
            if gcd(arr[i], arr[j]) == 1:
                count += 1
    return count

(বড় n-এ চালাকি দরকার হলে: প্রতিটা সংখ্যার count রেখে Euler phi / inclusion-exclusion দিয়ে O(max·log) করা যায় — কিন্তু সেটা Level 2-র গল্প।)

10. Thinking tweak

আসল "আহা!" মুহূর্ত এখানে efficiency-র চেয়ে correctness-এর: জোড়া গোনার সময় ভেতরের loop সবসময় i + 1 থেকে শুরু করো — এই একটা ছোট শর্তই দ্বিগুণ গোনা আর নিজে-জোড়া দুটো ভুল একসাথে আটকায়।

মূল মোচড়টা মনে গাঁথো: n জিনিস থেকে 2টা বাছার সংখ্যা n(n−1)/2, আর সেটা পেতে nested loop-এ ভেতরেরটা বাইরেরটার পরে শুরু করতে হয়। এই "upper-triangle only" প্যাটার্ন pair-ভিত্তিক যেকোনো problem-এ ফিরবে (closest pair, pair sum, ইত্যাদি)।

11. Step-by-step dry run

চলো arr = [2, 3, 4] ধীরে চালাই। count শুরুতে 0:

i	j	arr[i]	arr[j]	gcd	coprime?	count
0	1	2	3	1	হ্যাঁ	1
0	2	2	4	2	না	1
1	2	3	4	1	হ্যাঁ	2

বাইরের loop i = 0,1 (i = 2-এ ভেতরের loop খালি, কারণ j শুরু 3 থেকে যা n-এর বাইরে)। তিনটে জোড়া ঠিক একবার দেখা হলো, দুটো coprime — শেষ count = 2। section 5-এর ছকের সাথে হুবহু মিলল।

12. Python solution

from math import gcd


def count_coprime_pairs(arr):
    """arr-এর মধ্যে কতগুলো জোড়া (i < j) coprime (gcd == 1) — গোনে।"""
    n = len(arr)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):        # i < j: প্রতি জোড়া ঠিক একবার
            if gcd(arr[i], arr[j]) == 1:
                count += 1
    return count


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_coprime_pairs([2, 3, 4]) == 2          # (2,3),(3,4)
assert count_coprime_pairs([1, 2, 3, 4]) == 5       # 1 সবার সাথে + (2,3),(3,4)
assert count_coprime_pairs([6, 10, 15]) == 0        # প্রতি জোড়ায় common factor
assert count_coprime_pairs([5, 7, 11]) == 3         # তিনটেই prime
assert count_coprime_pairs([4]) == 0                # একটাই উপাদান
assert count_coprime_pairs([]) == 0                 # খালি list
assert count_coprime_pairs([2, 2, 3]) == 2          # (2,3) দুবার, (2,2) নয়
assert count_coprime_pairs([8, 9, 25]) == 3         # 2^3, 3^2, 5^2 -> সব coprime

print(count_coprime_pairs([2, 3, 4]))     # 2
print(count_coprime_pairs([1, 2, 3, 4]))  # 5
print(count_coprime_pairs([6, 10, 15]))   # 0
print("সব test pass!")

13. Line-by-line explanation

from math import gcd

Python-এর built-in gcd — 018-এর Euclid এখানে আবার লিখে রি-ইনভেন্ট করার দরকার নেই, ready টুল ব্যবহার করি।

    n = len(arr)
    count = 0

list-এর দৈর্ঘ্য রাখি, আর coprime জোড়ার গোনা 0 থেকে শুরু।

    for i in range(n):
        for j in range(i + 1, n):

দুই nested loop — এটাই সব জোড়া ঘোরার অংশ। গুরুত্বপূর্ণ: j শুরু i + 1 থেকে, যাতে (i, j) আর (j, i) দুবার না গোনা হয় আর i == j (নিজে-জোড়া) এড়ানো যায়।

            if gcd(arr[i], arr[j]) == 1:
                count += 1

প্রতিটা জোড়ায় gcd দেখি; ঠিক 1 হলে coprime, তাই count বাড়াই। শেষে return count।

বাকি assert লাইনগুলো নিজেদের চেক করছে (খালি list, একক উপাদান, prime-only সহ নানা ক্ষেত্র); সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

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

2
5
0
সব test pass!

প্রথম লাইন: [2,3,4] → 2 (section 11-এর dry run)। দ্বিতীয়: [1,2,3,4] → 5 — 1 প্রতিটা অন্যটার সাথে coprime (3টা জোড়া) + (2,3) + (3,4) = 5। তৃতীয়: [6,10,15] → 0, কারণ প্রতিটা জোড়ায় common factor। আগের সব assert চুপচাপ pass করেছে, তাই শেষে সব test pass!।

15. Time complexity

O(n² · log max) — জোড়ার সংখ্যা প্রায় n²/2 (nested loop), আর প্রতিটায় একটা gcd যার খরচ O(log max), যেখানে max হলো list-এর সবচেয়ে বড় সংখ্যা। ছোট-মাঝারি n-এ ঠিক আছে; বিশাল n-এ ধীর (তখন phi/Möbius লাগে)।

16. Space complexity

O(1) — শুধু count, i, j — গুটিকয় variable। কোনো বাড়তি list বা array বানাচ্ছি না; input list-টাই শুধু পড়ছি।

17. Common mistakes

1. প্রতিটা জোড়া দুবার গোনা — ভেতরের loop 0 থেকে শুরু করলে (i, j) আর (j, i) দুবার গোনা হবে, উত্তর দ্বিগুণ। সবসময় j = i + 1 থেকে।
2. উপাদানকে নিজের সাথে জোড়া বাঁধা — j যদি i থেকে শুরু হয়, তাহলে (i, i) জোড়াও গোনা হবে; gcd(x, x) = x, ভুল ফল। i + 1 এটা ঠেকায়।
3. শেষে দুবার-গোনা ভেবে 2 দিয়ে ভাগ করা — i < j ব্যবহার করলে আগে থেকেই একবার করে গোনা; আবার ভাগ করলে ভুল।
4. মান বনাম position গুলিয়ে ফেলা — [2, 2, 3]-এ দুটো 2 আলাদা position, তাই (2,3) দুবার গোনা ঠিক (উত্তর 2)। আমরা position-এর জোড়া গুনছি, distinct মানের নয়।
5. খালি/একক list ভুলে যাওয়া — n < 2 হলে কোনো জোড়াই নেই, উত্তর 0; loop এমনিতেই চলে না, তবু মাথায় রেখো।

18. Harder problems that inherit this idea

• CP-Algorithms — Euler's totient function (https://cp-algorithms.com/algebra/phi-function.html) — বড় n-এ coprime গোনার দ্রুত পথ phi/inclusion-exclusion দিয়ে আসে; আমাদের পরের problem 023-এর ভিত্তি।
• LeetCode — Number of Pairs ... GCD/coprime (https://leetcode.com/tag/number-theory/) — pair + number theory মিলিয়ে নানা variant; common interview pattern।
• 023 (Euler Phi Basic) — এই repo-রই পরের ধাপ, যেখানে "n-এর সাথে কয়টা coprime" এক সংখ্যার জন্য দ্রুত বের করা শিখব।

19. Pattern learned

Pairwise check with i < j — কোনো শর্ত (এখানে coprime, gcd == 1) সব জোড়ায় যাচাই করতে nested loop, ভেতরেরটা i + 1 থেকে শুরু করে প্রতিটা জোড়া ঠিক একবার। এই "upper-triangle" প্যাটার্ন যেকোনো pair-counting problem-এ ফিরবে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "সব জোড়ার coprime গোনা = nested loop, j শুরু i+1 থেকে, gcd == 1 হলে count++। জোড়া গোনার সময় সবসময় i < j — দ্বিগুণ গোনা আর নিজে-জোড়া একসাথে আটকায়। বড় n হলে phi/Möbius লাগবে (Level 2)।"

পরের ধাপ → 023 — Euler Phi Basic (এক সংখ্যার coprime বন্ধু দ্রুত গোনা)। শিকড় → 021 — Coprime Check।

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

---

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