Problem link ও উৎস
- Original source: Classic beginner exercise (HackerRank-style warmup)
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 0: Absolute Basics
- Difficulty: Easy
- Pattern: nested loops
- Basic idea inherited from: — (এটা আলাদা শাখার শুরু, আগের digit-problem থেকে আসেনি)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা সংখ্যা `n` দেওয়া আছে। তোমাকে `n`টা সারি (row) ছাপতে হবে, যেখানে সংখ্যাগুলো একটা সুন্দর pattern বানায়। সবচেয়ে চেনা pattern — একটা ত্রিভুজ:
```
1
1 2
1 2 3
1 2 3 4
```
মানে: ১ম সারিতে 1টা সংখ্যা, ২য় সারিতে 2টা, ... `i`-তম সারিতে `i`টা সংখ্যা। ব্যস, এই pattern-টা তৈরি করাই কাজ।
(আরও কয়েকটা variation আছে — একই সংখ্যা বারবার, উল্টো ত্রিভুজ — নিচে দেখব। মূল কৌশল সবগুলোতেই এক।)
### Input ও output {#6-example-input-and-output}
```text
input n = 4 -> output:
1
1 2
1 2 3
1 2 3 4
input n = 1 -> output:
1
input n = 0 -> output:
(কিছুই না — খালি, কোনো সারি নেই)
```
Edge case দুটো: **n = 1** → শুধু একটা সারি `1`; **n = 0** (বা negative) → একটাও সারি নয়, output সম্পূর্ণ খালি। loop ঠিকভাবে লিখলে এগুলো এমনিই সামলে যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **বইয়ের তাক (bookshelf)** সাজাচ্ছ — কয়েকটা থাক (shelf), প্রতিটা থাকে কিছু বই।
- বাইরের loop = "এখন কোন থাকে কাজ করছি" (থাক 1, থাক 2, ...) → সারি
- ভেতরের loop = "এই থাকে এক-একটা করে বই বসাচ্ছি" → ওই সারির সংখ্যাগুলো
- এক থাক ভরা শেষ হলে পরের থাকে যাও = সারি শেষে newline
ত্রিভুজে নিয়মটা শুধু এই — প্রথম থাকে 1টা বই, দ্বিতীয় থাকে 2টা, ... যত নিচে নামো তত বেশি বই। থাক (সারি) সামলায় বাইরের loop, বই (সংখ্যা) সামলায় ভেতরের loop।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এই problem-টা digit-extraction পরিবারের নয় — তাই "inherited from: —"। এটা Level 0-এর **আলাদা একটা শাখার শিকড়**: loop-এর ভেতরে loop।
আগের problem-গুলোতে (002-009) একটাই loop দিয়ে একটা সংখ্যার digit ধরে হাঁটতাম। এখানে উল্টো — সংখ্যা ভাঙছি না, বরং দুটো loop **একসাথে** চালিয়ে একটা দ্বিমাত্রিক (2D) আকৃতি বানাচ্ছি। তাই এটা নতুন একটা হাতিয়ার, যেটা থেকে পরে গজাবে: matrix ছাপা, grid-এ হাঁটা, multiplication table, এমনকি 2D dynamic programming-এর ভিত।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
এখানে গভীর কোনো গণিত-সূত্র নেই; মূল idea হলো **nested loop** — একটা loop-এর ভেতরে আরেকটা loop:
- **বাইরের loop** ঠিক করে কোন **সারি**-তে আছি (i = 1 থেকে n)
- **ভেতরের loop** ঠিক করে ওই সারিতে কোন কোন **সংখ্যা/কলাম** ছাপব (j = 1 থেকে i)
```
বাইরের loop i: 1 .. n # প্রতিটা সারি
ভেতরের loop j: 1 .. i # ওই সারির ভেতরের সংখ্যাগুলো
ছাপো j
সারি শেষ -> newline
```
ছোট গাণিতিক সত্য পাশে: মোট কতগুলো সংখ্যা ছাপা হলো? `1 + 2 + 3 + ... + n = n(n+1)/2` — এটাই বলে দেয় কাজের পরিমাণ (Section 15-এ লাগবে)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
এখানে "brute force বনাম optimal" ব্যাপারটা একটু আলাদা — কারণ pattern ছাপতে হলে প্রতিটা সংখ্যা ছাপতেই হবে, তাকানোর শর্টকাট নেই। তবে প্রথম, সবচেয়ে সরল ভাবনা — প্রতি সারিতে ভেতরের loop দিয়ে এক-একটা সংখ্যা **আলাদা করে** print করা:
```python
def print_triangle_brute(n):
for i in range(1, n + 1): # প্রতিটা সারি
for j in range(1, i + 1): # সারির ভেতরের সংখ্যা
print(j, end=" ") # একটা একটা ছাপো, পাশে ফাঁকা
print() # সারি শেষ -> পরের লাইনে যাও
```
এটা একদম সরাসরি pattern-টাকে code-এ অনুবাদ করে — দুটো loop, ভেতরে print। কাজ করে, পড়তেও সহজ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই version "ধীর" নয় algorithm-এর অর্থে — মোট `n(n+1)/2`টা সংখ্যা ছাপতে হলে, সেটুকু কাজ যেকোনো পদ্ধতিতেই লাগবে। কিন্তু **কীভাবে** ছাপছি, তাতে একটা ব্যবহারিক পার্থক্য আছে:
- **বারবার `print()` ডাকা ব্যয়বহুল:** প্রতিটা সংখ্যার জন্য আলাদা `print(j, end=" ")` ডাকা — output operation প্রতিবার একটু overhead নেয়। সংখ্যা অনেক হলে (বড় n) এটা টের পাওয়া যায়।
- **পরিচ্ছন্নতা:** প্রতি সারি এক-এক করে না ছেপে, পুরো সারিটা একটা string বানিয়ে **একবারে** ছাপলে code পরিষ্কার হয় আর print-call কমে।
মূল কথা ধীরগতি নয় — **ভেতরের loop-এ কাজটা সরাসরি print না করে আগে জমিয়ে নেওয়া** একটা ভালো অভ্যাস, যেটা পরে বড় output-এ কাজে দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
ভেতরের loop-এ সরাসরি না ছেপে, প্রতি সারির সংখ্যাগুলো আগে একটা **string-এ জমাই**, তারপর সারিপিছু একবার করে print:
```python
def print_triangle(n):
for i in range(1, n + 1):
row = " ".join(str(j) for j in range(1, i + 1)) # পুরো সারি একসাথে
print(row) # সারিপিছু একবার print
```
`" ".join(...)` সংখ্যাগুলোর মাঝে ফাঁকা বসিয়ে এক টুকরো string বানায় (যেমন `"1 2 3"`), তারপর সেটা একবারে ছাপি। print-call কমল (সারিপিছু একটা), trailing space-ও থাকে না — পরিষ্কার।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
মূল মোচড় এক বাক্যে: **বাইরের loop "কতগুলো সারি", ভেতরের loop "এই সারিতে কতদূর" — আর ভেতরের সীমা বাইরের চলক `i`-এর উপর নির্ভর করলেই ত্রিভুজ জন্ম নেয়।**
এই নির্ভরতাই (ভেতরের loop `range(1, i+1)`) আসল জাদু:
- ভেতরের loop যদি `1..i` হয় → সোজা ত্রিভুজ (নিচে বাড়ে)
- যদি `i..n` বা `1..(n-i+1)` হয় → উল্টো ত্রিভুজ (নিচে কমে)
- যদি `j`-এর বদলে `i` ছাপো → প্রতি সারিতে একই সংখ্যা (`1`, `2 2`, `3 3 3`...)
মানে কাঠামো এক — দুটো nested loop — শুধু **ভেতরের loop-এর সীমা আর কী ছাপছি** বদলেই হাজারটা pattern। মুখস্থ নয়, এই নির্ভরতাটা বোঝো।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 4`-এর ত্রিভুজ — কোন সারিতে i কত, ভেতরের loop j কতদূর যায়, পাশে দেখো:
```text
i = 1 : j: 1 -> "1" (1টা সংখ্যা)
i = 2 : j: 1 2 -> "1 2" (2টা সংখ্যা)
i = 3 : j: 1 2 3 -> "1 2 3" (3টা সংখ্যা)
i = 4 : j: 1 2 3 4 -> "1 2 3 4" (4টা সংখ্যা)
লক্ষ করো: ভেতরের loop j সবসময় 1 থেকে শুরু,
কিন্তু থামে i-তে -> তাই সারি যত নিচে, তত লম্বা
```
আরেকভাবে দেখো — কাজটা আসলে একটা ত্রিভুজাকার grid ভরা:
```text
j=1 j=2 j=3 j=4
i=1 : [1]
i=2 : [1] [2]
i=3 : [1] [2] [3]
i=4 : [1] [2] [3] [4]
^ ভেতরের loop ডানে বাড়ে, বাইরের loop নিচে নামে
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 3`-এ Section 9-এর version হাতে চালাই। বাইরের loop `i`-এর প্রতিটা মানে ভেতরে কী হয়, দেখো:
| i (বাইরের) | ভেতরের range(1, i+1) | j গুলো | row = " ".join | print |
| --- | --- | --- | --- | --- |
| 1 | range(1, 2) | 1 | `"1"` | 1 |
| 2 | range(1, 3) | 1, 2 | `"1 2"` | 1 2 |
| 3 | range(1, 4) | 1, 2, 3 | `"1 2 3"` | 1 2 3 |
তিনটা সারি ছাপা শেষ, বাইরের loop থামল। চূড়ান্ত output:
```text
1
1 2
1 2 3
```
এবার মনে মনে `n = 0` চালাও: `range(1, 1)` খালি, বাইরের loop **একবারও** চলে না → কিছুই ছাপে না। ঠিক, n = 0-এ output খালি — আলাদা if লাগে না।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def triangle_rows(n):
"""ত্রিভুজ pattern-টা list of string হিসেবে বানায় (print না করে)।
এতে test করা সহজ — প্রতিটা সারি যাচাই করা যায়।"""
rows = []
for i in range(1, n + 1):
row = " ".join(str(j) for j in range(1, i + 1))
rows.append(row)
return rows
def print_triangle(n):
"""ত্রিভুজটা সরাসরি ছাপে।"""
for row in triangle_rows(n):
print(row)
def same_number_rows(n):
"""variation: প্রতি সারিতে একই সংখ্যা (1 / 2 2 / 3 3 3 ...)।"""
return [" ".join([str(i)] * i) for i in range(1, n + 1)]
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert triangle_rows(4) == ["1", "1 2", "1 2 3", "1 2 3 4"]
assert triangle_rows(1) == ["1"]
assert triangle_rows(0) == [] # n = 0 -> খালি
assert triangle_rows(3) == ["1", "1 2", "1 2 3"]
assert same_number_rows(3) == ["1", "2 2", "3 3 3"]
assert same_number_rows(0) == []
# মোট সংখ্যা = n(n+1)/2 — সারিগুলোর শব্দ গুনে যাচাই
total = sum(len(r.split()) for r in triangle_rows(5))
assert total == 5 * 6 // 2 # 15
print("n = 4 ত্রিভুজ:")
print_triangle(4)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def triangle_rows(n):
rows = []
for i in range(1, n + 1):
```
প্রতিটা সারিকে আলাদা করে print না করে একটা list-এ জমাই — এতে পরে test-এ মিলিয়ে দেখা যায়। বাইরের loop `i` চলে 1 থেকে n পর্যন্ত (`range(1, n+1)` মানে n-ও ধরা)।
```
row = " ".join(str(j) for j in range(1, i + 1))
```
**এই problem-এর প্রাণ।** ভেতরের অংশ `range(1, i+1)` দেয় 1 থেকে `i` পর্যন্ত সংখ্যা — খেয়াল করো সীমাটা `i`-এর উপর নির্ভর করছে, এজন্যই সারি যত নিচে তত লম্বা। `str(j)` প্রতিটাকে string বানায়, `" ".join(...)` মাঝে ফাঁকা বসিয়ে এক সারির string গাঁথে।
```
rows.append(row)
return rows
```
বানানো সারিটা list-এ জমা, সব শেষে list ফেরত।
```
def print_triangle(n):
for row in triangle_rows(n):
print(row)
```
জমানো সারিগুলো এক-এক করে ছাপি — সারিপিছু একটাই `print`, পরিষ্কার।
```
def same_number_rows(n):
return [str(i)] * i ...
```
variation — এখানে `j`-এর বদলে `i` ছাপি, আর `[str(i)] * i` মানে "`i` লেখাটা `i` বার" (যেমন `["3","3","3"]`)। তাই `3 3 3`। কাঠামো একই, শুধু কী ছাপছি বদলালো।
বাকি `assert` গুলো — সারির তালিকা, edge case (n = 0), আর মোট সংখ্যার সূত্র `n(n+1)/2` — সব যাচাই করে; ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
n = 4 ত্রিভুজ:
1
1 2
1 2 3
1 2 3 4
সব test pass!
```
প্রথম লাইনটা শিরোনাম। তারপর `print_triangle(4)` চারটে সারি ছাপে — 1; 1 2; 1 2 3; 1 2 3 4 (i বাড়ার সাথে সারি লম্বা)। তার আগের সব `assert` (সারির তালিকা, n = 0 খালি, variation, যোগফল 15) চুপচাপ pass করেছে। শেষ লাইন `সব test pass!` — সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n²)** — বাইরের loop n বার, ভেতরের loop গড়ে n/2 বার, মোট কাজ `1 + 2 + ... + n = n(n+1)/2` ≈ `n²/2`টা সংখ্যা ছাপা। n দ্বিগুণ হলে কাজ প্রায় চারগুণ। এটা pattern-এর স্বভাবগত — মোট এতগুলো সংখ্যা ছাপতে হলে এর কমে হয় না।
### অতিরিক্ত জায়গা {#16-space-complexity}
- শুধু ছাপলে (`print_triangle` সরাসরি): **O(n)** — এক সময়ে একটা সারির string (সর্বোচ্চ n-টা সংখ্যা) মেমরিতে থাকে।
- পুরো তালিকা ফেরালে (`triangle_rows`): **O(n²)** — সব সারি একসাথে রাখলে মোট `n(n+1)/2`টা সংখ্যার string জমে।
(শুধু console-এ ছাপা হলে অনেকে একে O(1) auxiliary-ও বলে, কারণ ছাপার পর কিছু রাখি না।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`range` সীমায় off-by-one** — `range(1, n+1)` লিখতে হয় n-কে ধরতে; `range(1, n)` লিখলে শেষ সারিটা বাদ পড়ে। আর ভেতরে `range(1, i+1)`, `range(1, i)` নয়। এটাই এক নম্বর ভুল।
2. **`print()` দিয়ে newline ভুলে যাওয়া** — ভেতরের loop শেষে সারি ভাঙতে newline দরকার; না দিলে সব সংখ্যা এক লাইনে লেপ্টে যায়। (string-জমানো version-এ `print(row)` নিজেই newline দেয়, তাই এ ভুল হয় না।)
3. **ভেতরের সীমা `i`-এর বদলে `n` দেওয়া** — `range(1, n+1)` ভেতরে দিলে ত্রিভুজ না হয়ে আয়তক্ষেত্র (সব সারি সমান লম্বা) হয়ে যাবে। ভেতরের loop-কে `i`-এর উপর নির্ভর করতেই হবে।
4. **`i` আর `j` গুলিয়ে ফেলা** — কোন সংখ্যা ছাপছি (`j`) আর কোন সারিতে আছি (`i`) — গুলিয়ে ফেললে pattern বদলে যায়।
5. **n = 0 / negative নিয়ে দুশ্চিন্তা** — আলাদা if লাগে না; `range(1, 0+1)` = `range(1, 1)` খালি, loop এমনিই চলে না।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **HackerRank — Staircase** (