Problem link ও উৎস
- **Original source:** Classic Nim game; LeetCode Nim Game (single-pile take-1-to-3 variant)
- **Platform:** LeetCode —
; CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
- **Difficulty:** Medium
- **Pattern:** XOR theorem (Nim-value of piles)
- **Basic idea inherited from:** 141 (W/L labeling), 060 (XOR)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কয়েকটা স্তূপ (pile) পাথর — যেমন `[3, 4, 5]`। দুই player পালা করে চাল দেয়। প্রতি চালে যে কেউ **যেকোনো একটা** pile বেছে তা থেকে **যত খুশি** (অন্তত 1টা) পাথর সরায়। যে আর চাল দিতে পারে না (সব pile খালি, তার পালা) সে হারে (normal play)।
দুজনেই নিখুঁত খেলে। জিজ্ঞেস: **প্রথম player জিতবে কি?**
আশ্চর্যের ব্যাপার — উত্তরটা একটাই সংখ্যা দেখলেই বলা যায়: সব pile-এর **XOR**। আর LeetCode-এর সরল রূপটা single-pile: `n` পাথর, প্রতি চালে 1/2/3টা — সেখানে উত্তর `n % 4`-এ ধরা (141-এর সেই pattern!)।
> এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে XOR theorem-এর eleganceটা উপভোগ করবে।
### Input ও output {#6-example-input-and-output}
```text
piles XOR প্রথম player
-----------------------------------------------------
[3, 4, 5] 3^4^5 = 2 ≠ 0 জেতে (W)
[1, 2, 3] 1^2^3 = 0 হারে (L)
[0, 0, 0] 0 হারে (L) — চাল-ই নেই
[7] 7 ≠ 0 জেতে (W) — পুরোটা নিয়ে নাও
[5, 5] 5^5 = 0 হারে (L) — আয়না জোড়া
single-pile (LeetCode, take 1-3):
n = 4 n % 4 == 0 হারে (L)
n = 1, 2, 3 n % 4 != 0 জেতে (W)
```
দুটো edge case: সব pile **0** হলে XOR 0 → L (চাল নেই); আর দুটো **সমান** pile (`[5,5]`) XOR 0 → L (একটা আয়না-জোড়া)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুটো আয়না-খেলা। তোমার সামনে কয়েকটা মোমবাতির সারি (pile), আর তোমার প্রতিপক্ষ এক "আয়নাধারী" — সে তোমার প্রতিটা চালের আয়না-জবাব দিতে চায়, যাতে শেষে সারিটা আবার "ভারসাম্যে" (XOR = 0) ফিরে আসে।
- শুরুতে যদি ভারসাম্য থাকে (XOR = 0), তুমি যা-ই চাল দাও তা ভারসাম্য ভাঙবে, আর প্রতিপক্ষ সবসময় আবার ভারসাম্যে ফিরিয়ে আনতে পারবে — তুমি ফাঁদে, শেষে চাল-হীন তুমিই (L)।
- শুরুতে ভারসাম্য না থাকলে (XOR ≠ 0), **তুমিই** এক চালে ভারসাম্য বানিয়ে আয়নাধারী হয়ে যাও — এবার প্রতিপক্ষ ফাঁদে (W)।
মূল কথা: যে ভারসাম্য (XOR = 0) **বানাতে পারে**, সে-ই জেতে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো শিকড়: **W/L labeling** (problem 141) আর **XOR** (problem 060)। 141 থেকে এসেছে "প্রতিটা position W না L" — এই কাঠামোটাই। কিন্তু Nim-এ state হলো `(pile₁, pile₂, ...)` — এত state যে পুরো table ভরা অসম্ভব। তখনই XOR theorem উদ্ধার করে: পুরো backward induction-এর ফলাফলটা একটা সূত্রে নেমে আসে।
আর XOR-এর স্বভাব (060): `a ^ a = 0`, `a ^ 0 = a`, এবং bitwise স্বাধীনতা — এগুলোই theorem-এর প্রমাণের ইট। তাই Nim হলো 141-এর W/L আর 060-এর XOR-এর সুন্দর মিলন।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা **Nim XOR theorem**:
```text
সব pile-এর XOR ≠ 0 ⟺ যার চাল সে জেতে (W position)
সব pile-এর XOR = 0 ⟺ যার চাল সে হারে (L position)
```
কেন XOR, কেন যোগফল নয়? কারণ XOR প্রতিটা bit-কে আলাদাভাবে দেখে — কোনো bit-position-এ যদি জোড়সংখ্যক pile-এ সেই bit জ্বলে থাকে, তারা পরস্পরকে "বাতিল" করে। XOR = 0 মানে প্রতিটা bit-position-এ ভারসাম্য — আর এই ভারসাম্যই হারা-অবস্থার চিহ্ন। যোগফল এই bit-ভারসাম্য ধরতে পারে না, তাই কাজ করে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
XOR theorem না জানলে, 141-এর মতো সরাসরি W/L recursion করা যায় — state এখন pile-গুলোর tuple:
```python
from functools import lru_cache
def nim_brute(piles):
piles = tuple(sorted(piles))
@lru_cache(maxsize=None)
def win(state):
for i, p in enumerate(state):
for take in range(1, p + 1): # i-তম pile থেকে take সরাও
ns = list(state)
ns[i] -= take
ns = tuple(sorted(ns))
if not win(ns): # opponent L-এ
return True
return False # সব চাল W-তে -> L
return win(piles)
```
এটা definition-এর হুবহু — ঠিক উত্তর দেয়, আর XOR theorem যাচাইয়ের মাপকাঠি হিসেবে দারুণ। কিন্তু state-সংখ্যা বিস্ফোরক।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
State হলো প্রতিটা pile-এর মানের সব সম্ভাব্য combination। `k`টা pile, প্রতিটা সর্বোচ্চ `M` — মোট state প্রায় `M^k`:
```text
3 pile, প্রতিটা ≤ 100 -> ~100^3 = 10 লাখ state (memo লাগবেই)
pile বড় হলে (≤ 10^9) -> অসম্ভব — state গোনাই যায় না
XOR theorem -> O(k), পুরো recursion এক সূত্রে নেমে এল
```
মূল শিক্ষা: backward induction-এর পুরো গাছটা XOR theorem একটা `O(k)` হিসাবে গুটিয়ে দেয় — এটাই theorem-এর শক্তি।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight (theorem): শুধু সব pile-এর **XOR** বের করো; `≠ 0` হলে প্রথম player W, `= 0` হলে L। ব্যস।
কেন? দুই দিক:
- **XOR = 0 হলে:** যেকোনো চালে তুমি কোনো এক pile কমাও → সেই pile-এর bit বদলায় → XOR আর 0 থাকে না (ভারসাম্য ভাঙে)। প্রতিপক্ষ সবসময় আবার XOR = 0 করতে পারে। শেষ (সব 0, XOR = 0) আসে প্রতিপক্ষের চালের পরে — চাল-হীন তুমি (L)।
- **XOR ≠ 0 হলে:** সবচেয়ে বড় জ্বলা bit-ওয়ালা pile-টা এমনভাবে কমাও যে নতুন XOR = 0 — এমন চাল **সবসময় থাকে**। তুমি ভারসাম্য বানিয়ে আয়নাধারী হলে (W)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা": **pile-এর যোগফল ভুলে যাও — সব pile-এর XOR-ই একমাত্র সত্য; XOR ≠ 0 মানে তুমি জেতার চাল বানাতে পারো।**
ফাঁদ দুটো: (১) XOR-এর বদলে sum দেখা — sum কিছুই বলে না (concept-notes mistake #4); (২) **misère variant** (শেষ পাথর নিলে হার) আলাদা নিয়ম — গুলিয়ো না। আর LeetCode-এর single-pile take-1-to-3 রূপটা আসলে 141-এর সেই game — উত্তর `n % 4`-এ; এটাকে multi-pile XOR Nim-এর সাথে মিশিয়ো না (নিয়ম আলাদা)।
### ছবিতে বোঝা {#5-visual-explanation}
XOR কীভাবে bit-ভারসাম্য মাপে (`[3, 4, 5]`):
```text
pile গুলো binary-তে সাজাও, প্রতিটা bit-column আলাদা গোনো:
bit2 bit1 bit0
3 = 0 1 1
4 = 1 0 0
5 = 1 0 1
-----------------------
XOR = 0 1 0 = 2 (≠ 0 -> প্রথম player W)
column-এ 1-এর সংখ্যা জোড় হলে XOR-bit 0, বিজোড় হলে 1।
XOR = 2 ≠ 0 -> ভারসাম্য নেই -> W
তুলনায় [1, 2, 3]:
1 = 001, 2 = 010, 3 = 011
XOR = 001 ^ 010 ^ 011 = 000 = 0 -> ভারসাম্য -> L (প্রথম player ফাঁদে)
```
লক্ষ করো — যোগফল (`3+4+5=12`) কিছুই বলে না; শুধু **column-by-column XOR**-ই সত্য বলে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`[1, 2, 3]` (XOR = 0, তাই L) — দেখাই কেন প্রথম player হারে:
1. **XOR হিসাব:** `1 ^ 2 ^ 3` = `001 ^ 010 ^ 011` = `000` = 0 → প্রথম player L।
2. প্রথম player যা-ই করুক, ভারসাম্য ভাঙবে। ধরো সে pile 3 থেকে 2 নিল → `[1, 2, 1]`, XOR = `001 ^ 010 ^ 001` = `010` = 2 ≠ 0।
3. **আয়না-জবাব:** দ্বিতীয় player XOR আবার 0 করে — pile 2 (মান 2) থেকে 2 নিয়ে `[1, 0, 1]`, XOR = `001 ^ 000 ^ 001` = 0।
4. প্রথম player আবার ভাঙে → ধরো pile 0 থেকে 1 নিল → `[0, 0, 1]`, XOR = 1।
5. দ্বিতীয় player শেষ pile-এর 1 নিয়ে `[0, 0, 0]` — সব খালি। এখন প্রথম player-এর পালা, চাল নেই → **প্রথম player হারল (L)**। ✓ theorem ঠিক।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def nim_first_player_wins(piles):
"""multi-pile Nim: সব pile-এর XOR ≠ 0 হলে প্রথম player জেতে।"""
x = 0
for p in piles:
x ^= p
return x != 0
def leetcode_nim_can_win(n):
"""single-pile, প্রতি চালে 1/2/3: n % 4 != 0 হলে প্রথম player জেতে।"""
return n % 4 != 0
from functools import lru_cache
def nim_brute(piles):
"""সরল W/L recursion — XOR theorem যাচাইয়ের জন্য।"""
piles = tuple(sorted(piles))
@lru_cache(maxsize=None)
def win(state):
for i, p in enumerate(state):
for take in range(1, p + 1):
ns = list(state)
ns[i] -= take
if not win(tuple(sorted(ns))):
return True
return False
return win(piles)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert nim_first_player_wins([3, 4, 5]) is True # 3^4^5 = 2 ≠ 0
assert nim_first_player_wins([1, 2, 3]) is False # 1^2^3 = 0
assert nim_first_player_wins([0, 0, 0]) is False # চাল নেই
assert nim_first_player_wins([7]) is True
assert nim_first_player_wins([5, 5]) is False # আয়না জোড়া
# brute force-এর সাথে এলোমেলো ছোট case-এ মিল (theorem-এর প্রমাণ)
import random
for _ in range(400):
k = random.randint(1, 3)
piles = tuple(random.randint(0, 5) for _ in range(k))
assert nim_first_player_wins(piles) == nim_brute(piles), piles
# single-pile LeetCode version
for n in range(20):
assert leetcode_nim_can_win(n) == (n % 4 != 0), n
print(nim_first_player_wins([3, 4, 5])) # True
print(nim_first_player_wins([1, 2, 3])) # False
print(leetcode_nim_can_win(4)) # False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
x = 0
for p in piles:
x ^= p
return x != 0
```
এটাই পুরো theorem। `x` শুরুতে 0; প্রতিটা pile XOR করে যোগ করি (`x ^= p`)। শেষে `x ≠ 0` মানে ভারসাম্য নেই → প্রথম player জেতে। মাত্র `O(k)`।
```text
def leetcode_nim_can_win(n):
return n % 4 != 0
```
LeetCode-এর single-pile take-1-to-3 — এটা multi-pile XOR Nim নয়, বরং 141-এর সেই subtraction game; উত্তর `n % 4`-এ (4-এর গুণিতকে L)।
```text
@lru_cache(maxsize=None)
def win(state):
...
if not win(tuple(sorted(ns))):
return True
```
brute version — প্রতিটা pile থেকে সম্ভাব্য সব `take` চেষ্টা করি; কোনোটা opponent-কে L-এ ফেললে আমি W। `sorted` করে `lru_cache` দিয়ে একই state বারবার গোনা এড়াই।
বাকি `assert` গুলো তিনভাবে যাচাই: (১) হাতে-গোনা ছোট case, (২) 400টা random pile-এ brute force-এর সাথে মিল, (৩) single-pile `n % 4`। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
True
False
False
সব test pass!
```
প্রথম লাইন `[3,4,5]` → XOR 2 ≠ 0 → True (W)। দ্বিতীয় `[1,2,3]` → XOR 0 → False (L)। তৃতীয় single-pile `n=4` → False (4-এর গুণিতক, L)। তার আগের 400+টা `assert` চুপচাপ pass করেছে — theorem আর brute force সবসময় একমত। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(k)** — `k`টা pile একবার XOR করা, ব্যস। pile-এর মান যত বড়ই হোক (10⁹), XOR constant-time প্রতি pile। single-pile version **O(1)** (শুধু `n % 4`)। brute force ছিল প্রায় `O(M^k)` — সূত্র সেটাকে `O(k)`-তে নামিয়েছে।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু একটা accumulator `x`। কোনো array বা recursion stack লাগে না (theorem version-এ)। brute version অবশ্য memo-র জন্য `O(state)` নেয়, কিন্তু আসল solution সেটা নয়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **XOR-এর বদলে sum দেখা** — যোগফল কিছুই বলে না; শুধু XOR সত্য (concept-notes mistake #4)।
2. **Misère variant গুলিয়ে ফেলা** — "শেষ পাথর নিলে হার" আলাদা নিয়ম (সেখানে সব pile ≤ 1-এর special case); এখানে normal play।
3. **Single-pile আর multi-pile মিশিয়ে ফেলা** — LeetCode take-1-to-3 single-pile = `n % 4`; multi-pile any-amount = XOR। নিয়ম ভিন্ন।
4. **খালি pile (0) বাদ দেওয়া** — `0`-ও XOR-এ যায় (`x ^ 0 = x`), তাই আলাদা handle লাগে না; কিন্তু "pile আছে কিন্তু 0" আর "pile নেই" গুলিয়ো না।
5. **জেতার চাল খুঁজতে গিয়ে ভুল bit** — XOR ≠ 0-এ জেতার চাল = সর্বোচ্চ জ্বলা bit-ওয়ালা pile কমানো; অন্য pile কমালে সবসময় কাজ নাও করতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Nim Game** (