# Concept Notes — Absolute Basics

## সহজ করে শুরু: সংখ্যাকে ছোট অংশে ভাঙা

আগে `%` দিয়ে ভাগশেষ এবং `//` দিয়ে পূর্ণসংখ্যার ভাগফল বোঝো। `472 % 10 = 2`, আর `472 // 10 = 47`: একই সংখ্যার শেষ অঙ্ক নেওয়া ও সরানো হলো দুটো আলাদা কাজ। এই দুই কাজের loop থেকেই অঙ্কের যোগ, উল্টো সংখ্যা ও palindrome তৈরি হয়।

**প্রোগ্রামে কোথায় ব্যবহার করবে:** সংখ্যার ID-এর অঙ্ক পরীক্ষা, সাধারণ checksum শেখা এবং digit-ভিত্তিক input validation-এ এই কৌশল কাজে লাগে। ফোন নম্বর বা শুরুর শূন্য দরকার এমন ID-কে integer বানাবে না; string রাখবে।

**কৌশল বাছার আগে শর্ত:** `n = 0`-এর একটি অঙ্ক আছে। ঋণাত্মক সংখ্যায় আগে সমস্যার নিয়ম ঠিক করো; শুধু `while n > 0` লিখে সব input সামলানো যায় না।

পড়ার ক্রম: এই পরিচয় → নিচের বিস্তারিত ধারণা → [চিত্রে হাতে-কলমে হিসাব](visualization-ideas.md) → [সমস্যার তালিকা](problems/README.md)। প্রতিটি উদাহরণে আগে input, পরে বদলানো state, শেষে output মেলাও।

> এই file টা ধীরে পড়ো। প্রতিটা code snippet-এর পরে একটা mini dry run আছে — সেটা খাতায় নিজে হাতে আবার করো। Dry run করাটাই আসল শেখা।

## 1. সংখ্যা মানে digit-এর সারি

আমরা যখন `1234` লিখি, আসলে লিখি:

```
1234 = 1×1000 + 2×100 + 3×10 + 4×1

position:   thousands  hundreds  tens  ones
digit:          1          2       3     4
```

প্রতিটা digit একটা নির্দিষ্ট জায়গায় বসে আছে, আর জায়গাটা ঠিক করে দেয় সে কত "ওজন" বহন করছে। এটাকে বলে place value। পুরো level 0 এই একটা ছবির উপর দাঁড়িয়ে — সংখ্যা মানে digit-এর সারি, আর আমরা শিখব সেই সারি ধরে ডান থেকে বামে হাঁটতে।

## 2. `%` আর `//` — দুই power tool

ভাগ করলে দুটো জিনিস পাওয়া যায়: **quotient** (ভাগফল) আর **remainder** (ভাগশেষ)। Python-এ:

- `a // b` → quotient (integer division, ভগ্নাংশ ফেলে দেয়)
- `a % b` → remainder (modulo)

Analogy: তোমার কাছে 17টা চকলেট, 5 জন বন্ধুকে সমান ভাগ করে দিচ্ছ। প্রত্যেকে পাবে `17 // 5 = 3` টা, আর তোমার হাতে থেকে যাবে `17 % 5 = 2` টা। `//` বলে "প্রত্যেকে কত পেল", `%` বলে "কত বাকি রইল"।

```python
n = 1234
print(n % 10)   # 4  -> last digit!
print(n // 10)  # 123 -> last digit ফেলে দেওয়া সংখ্যা
```

**Mini dry run:** `1234 % 10` — 1234 কে 10 দিয়ে ভাগ করলে quotient 123, remainder 4। মানে `% 10` সবসময় **last digit** দেয়, আর `// 10` last digit **কেটে ফেলে**। এই জোড়াটাই আমাদের digit-কাটার কাঁচি।

```
1234 --%10--> 4 (পেলাম)     1234 --//10--> 123 (বাকি রইল)
 123 --%10--> 3              123 --//10--> 12
  12 --%10--> 2               12 --//10--> 1
   1 --%10--> 1                1 --//10--> 0  (শেষ!)
```

## 3. Digit extraction loop — সবচেয়ে দরকারি loop

উপরের ছবিটাকেই code বানালে:

```python
n = 1234
total = 0
while n > 0:
    d = n % 10      # last digit তুলে নাও
    total += d      # কাজে লাগাও (এখানে: যোগ করো)
    n //= 10        # last digit ফেলে দাও
print(total)        # 10
```

**Mini dry run:**

| step | n (শুরুতে) | d = n % 10 | total | n //= 10 |
| --- | --- | --- | --- | --- |
| 1 | 1234 | 4 | 4 | 123 |
| 2 | 123 | 3 | 7 | 12 |
| 3 | 12 | 2 | 9 | 1 |
| 4 | 1 | 1 | 10 | 0 |

`n` 0 হয়ে গেল, loop শেষ। `total = 10` — ঠিক 1+2+3+4।

এই একই কাঠামো দিয়ে digit count, digit-এর সর্বোচ্চ digit, even digit গোনা — সব হয়। শুধু "কাজে লাগাও" লাইনটা বদলায়। **এই loop-টা তোমার প্রথম reusable pattern।**

## 4. Parity — even না odd?

Even মানে 2 দিয়ে নিঃশেষে ভাগ যায়, odd মানে remainder 1 থাকে।

```python
n = 7
if n % 2 == 0:
    print("even")
else:
    print("odd")
```

**Mini dry run:** `7 % 2` — 7 = 2×3 + 1, remainder 1, তাই odd। `10 % 2` — 10 = 2×5 + 0, remainder 0, তাই even।

মজার ব্যাপার: binary-তে দেখলে একটা সংখ্যার **last bit**-ই বলে দেয় সে even না odd।

```
6  = 110  (last bit 0 -> even)
7  = 111  (last bit 1 -> odd)
12 = 1100 (last bit 0 -> even)
```

কেন? কারণ binary-তে শুধু last bit-টাই 1-এর ঘর; বাকি সব ঘর 2, 4, 8... — সবই even। তাই `n % 2` আর `n & 1` (last bit পড়া) একই উত্তর দেয়। এটা পরে bit manipulation-এ কাজে লাগবে — এখন শুধু connection টা মনে রাখো।

## 5. Number বানানো — `rev = rev * 10 + d`

Digit ভাঙা শিখলাম, এবার উল্টোটা: digit জুড়ে সংখ্যা বানানো। মূল কৌশল — পুরোনো সংখ্যাকে এক ঘর বামে ঠেলে (×10) নতুন digit-টা ডানে বসাও।

```python
n = 1234
rev = 0
while n > 0:
    d = n % 10
    rev = rev * 10 + d   # বামে ঠেলো, নতুন digit বসাও
    n //= 10
print(rev)               # 4321
```

**Mini dry run:**

| step | d | rev * 10 + d | rev (পরে) |
| --- | --- | --- | --- |
| 1 | 4 | 0×10 + 4 | 4 |
| 2 | 3 | 4×10 + 3 | 43 |
| 3 | 2 | 43×10 + 2 | 432 |
| 4 | 1 | 432×10 + 1 | 4321 |

Analogy: একটা সারিতে লোক দাঁড় করাচ্ছ। নতুন কেউ এলে আগের সবাই এক ধাপ বামে সরে (×10), নতুন জন ডান প্রান্তে দাঁড়ায় (+d)। ডান থেকে digit তুলেছিলাম, তাই বানানো সংখ্যাটা reverse হয়ে গেল — যে digit আগে বেরিয়েছে সে সবচেয়ে বামে চলে গেছে।

## 6. Palindrome = reverse-এর সাথে মিল

Palindrome number মানে উল্টে পড়লেও একই থাকে — 121, 1331, 7। আর আমরা তো reverse বানাতে শিখেই গেছি! তাহলে:

```python
def is_palindrome(n):
    if n < 0:
        return False        # -121 উল্টালে 121-, মেলে না
    original = n            # copy রাখো! n তো ভেঙে যাবে
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n //= 10
    return rev == original
```

**Mini dry run (n = 121):** rev ধাপে ধাপে 1 → 12 → 121। শেষে `121 == 121` → True। আর n = 123 হলে rev = 321, `321 != 123` → False।

লক্ষ করো `original = n` লাইনটা — reverse loop চালালে `n` শূন্য হয়ে যায়, তাই আগেই copy রাখা জরুরি। এটা না করা level 0-এর সবচেয়ে কমন bug।

## 7. Armstrong number = digit-power sum

153 একটা মজার সংখ্যা: এর 3টা digit, আর `1³ + 5³ + 3³ = 1 + 125 + 27 = 153` — নিজের কাছেই ফিরে আসে! এ ধরনের সংখ্যাকে Armstrong number বলে: প্রতিটা digit-কে (digit সংখ্যা)-তম power-এ তুলে যোগ করলে original সংখ্যাই পাওয়া যায়।

```python
def is_armstrong(n):
    k = len(str(n))         # কয়টা digit (এখানে str shortcut নিলাম)
    total, temp = 0, n
    while temp > 0:
        d = temp % 10
        total += d ** k
        temp //= 10
    return total == n
```

**Mini dry run (n = 153, k = 3):** d গুলো আসে 3, 5, 1 ক্রমে → total = 27 → 27+125 = 152 → 152+1 = 153। শেষে `153 == 153` → True। আবার সেই চেনা digit extraction loop — শুধু "কাজে লাগাও" অংশে এবার `d ** k`।

## 8. Digital root — mod 9-এর জাদু

Digital root: digit গুলো যোগ করো, ফলাফল এক digit না হওয়া পর্যন্ত আবার যোগ করো। যেমন 9875 → 9+8+7+5 = 29 → 2+9 = 11 → 1+1 = 2।

Loop দিয়ে লিখলে:

```python
def digital_root(n):
    while n >= 10:
        s = 0
        while n > 0:
            s += n % 10
            n //= 10
        n = s
    return n
```

কিন্তু একটা গোপন pattern আছে। টেবিলটা দেখো:

```
n:        1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19
d-root:   1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1
n % 9:    1  2  3  4  5  6  7  8  0  1  2  3  4  5  6  7  8  0  1
```

Digital root টা 1 থেকে 9 ঘুরে ঘুরে আসছে, আর `n % 9`-ও প্রায় একই — শুধু যেখানে digital root 9, সেখানে `n % 9` হয় 0। তাই one-liner:

```python
def digital_root_fast(n):
    return 0 if n == 0 else 1 + (n - 1) % 9
```

**Mini dry run (n = 9875):** `(9875 - 1) % 9 = 9874 % 9`। 9874 = 9×1097 + 1, তাই remainder 1, উত্তর `1 + 1 = 2` — loop version-এর সাথে মিলে গেল! কেন কাজ করে? কারণ `10 % 9 = 1`, তাই 9-এর জগতে প্রতিটা digit-এর place value-ই 1 — মানে সংখ্যা আর তার digit sum, mod 9-এ একই। এই idea-টাই পরে Level 2 (modular arithmetic)-এ পুরোপুরি খুলে দেখব।

## 9. Pattern printing = nested loop মানে grid

Nested loop-কে অনেকে ভয় পায়। ভয়ের কিছু নেই — nested loop মানে শুধু একটা **grid**: বাইরের loop ঠিক করে কোন **row**-তে আছি, ভেতরের loop সেই row-তে কয়টা জিনিস বসবে।

```python
n = 4
for row in range(1, n + 1):       # প্রতিটা row-র জন্য
    for col in range(1, row + 1): # সেই row-তে row-সংখ্যক ঘর
        print(col, end=" ")
    print()                       # row শেষ, নতুন লাইনে যাও
```

Output:

```
1
1 2
1 2 3
1 2 3 4
```

**Mini dry run:** row=1 হলে ভেতরের loop চলে col=1 পর্যন্ত → ছাপে `1`। row=2 হলে col যায় 1, 2 → ছাপে `1 2`। ভেতরের loop-এর সীমা (`row + 1`) বাইরের variable-এর উপর depend করছে — এজন্যই triangle হলো, square না। এই "ভেতরের সীমা বাইরের উপর নির্ভর করে" idea-টা পরে complexity analysis-এও ফিরবে (এ ধরনের loop মোট 1+2+...+n = n(n+1)/2 বার চলে)।

## 10. Python-এ int unbounded — overflow চিন্তা নেই

C++/Java-তে `int`-এর একটা সীমা আছে (32-bit int সর্বোচ্চ প্রায় 2.1×10⁹); সীমা ছাড়ালে overflow হয়ে ভুল উত্তর আসে। Python-এ int **unbounded** — যত বড় খুশি:

```python
print(2 ** 100)
# 1267650600228229401496703205376  — দিব্যি চলে!
```

তাই এই level-এ overflow নিয়ে চিন্তা নেই। কিন্তু দুটো কথা মাথায় রেখো: (1) LeetCode Reverse Integer-এর মতো problem ইচ্ছে করে 32-bit সীমা চাপিয়ে দেয় — তখন Python-এও নিজে check করতে হয়; (2) খুব বড় সংখ্যায় Python-এর arithmetic ধীর হয়ে যায় — এজন্যই Level 2-তে আমরা প্রতি step-এ mod নেওয়া শিখব।

## এক নজরে (cheat sheet)

```
n % 10          -> last digit
n // 10         -> last digit বাদ
n % 2 == 0      -> even (last bit 0)
rev*10 + d      -> ডানে digit জোড়া
while n > 0     -> digit extraction-এর খাঁচা
1 + (n-1) % 9   -> digital root shortcut
nested loop     -> grid: বাইরে row, ভেতরে column
```

পরের ধাপ: এই tool গুলো হাতে নিয়ে [problems/](problems/README.md)-এর 10টা problem। তারপর Level 1-এ গিয়ে দেখব `%` operator divisibility আর prime-এর জগতে কী কী করতে পারে।