Problem link ও উৎস
- **Original source:** LeetCode — Integer Break
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 8: Greedy Math Tricks
- **Difficulty:** Medium
- **Pattern:** break into 3s (সংখ্যাকে যথাসম্ভব 3-এর টুকরোয় ভাগ করা)
- **Basic idea inherited from:** — (এই শাখার স্বাধীন গোড়া)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক পূর্ণসংখ্যা `n` (≥ 2) দেওয়া। একে **অন্তত দুটো** ধনাত্মক পূর্ণসংখ্যার যোগফল হিসেবে ভাঙতে হবে (যেমন `n = 10` হলে `3 + 3 + 4`, বা `5 + 5`, বা `2 + 8`, ...)। প্রতিটা ভাঙার জন্য টুকরোগুলোর **গুণফল** হিসাব করো। প্রশ্ন — সব সম্ভব ভাঙার মধ্যে সবচেয়ে বড় গুণফল কত?
উদাহরণ: `n = 10`। `3 + 3 + 4 → 3 × 3 × 4 = 36`; `5 + 5 → 25`; `2 + 2 + 2 + 2 + 2 → 32`। এদের মধ্যে 36 সবচেয়ে বড়, তাই উত্তর **36**।
শর্তটা খেয়াল করো — অন্তত দুই টুকরো **লাগবেই** (পুরো `n`-কে এক টুকরো রেখে দেওয়া যাবে না)। তাই `n = 2`-এ একমাত্র ভাঙা `1 + 1 → 1`, আর `n = 3`-এ সেরা `1 + 2 → 2` (পুরো 3 রাখা বারণ)।
### Input ও output {#6-example-input-and-output}
```text
n output সেরা ভাঙা
-----------------------------------------------------------
2 1 1 + 1 (একমাত্র উপায়)
3 2 1 + 2 (পুরো 3 রাখা বারণ)
4 4 2 + 2
5 6 2 + 3
6 9 3 + 3
7 12 3 + 4 (বা 3+2+2)
8 18 3 + 3 + 2
9 27 3 + 3 + 3
10 36 3 + 3 + 4
```
মূল edge case দুটো **ছোট সংখ্যায়**: `n = 2` (→ 1) আর `n = 3` (→ 2)। এই দুটোতে greedy-র "3 বানাও" সরাসরি খাটে না — কারণ অন্তত দুই টুকরো করার বাধ্যবাধকতায় পুরো সংখ্যাটা একা রাখা যায় না। তাই এদের আলাদা করে handle করতে হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার হাতে `n` মিটার লম্বা একটা দড়ি, আর তুমি সেটা কয়েক টুকরো করে কাটবে। প্রতিটা টুকরো দিয়ে একটা করে বর্গাকার বেড়া বানাবে, আর তোমার "স্কোর" = সব বেড়ার ক্ষেত্রফলের গুণফল। কীভাবে কাটলে স্কোর সর্বোচ্চ?
খুব ছোট টুকরো (1 মিটার) বাজে — গুণফলে 1 দিয়ে গুণ করলে কিছুই বাড়ে না, বরং দড়ি নষ্ট। খুব বড় টুকরোও বাজে — একটা বড় টুকরোকে দুই-তিন টুকরো করলে গুণফল বাড়ে (কারণ গুণ যোগের চেয়ে দ্রুত বাড়ে)। মাঝামাঝি একটা "সোনালি মাপ" আছে — সেটা 3-এর কাছাকাছি (গণিতে আসল সর্বোত্তম `e ≈ 2.718`, পূর্ণসংখ্যায় তার নিকটতম 3)। তাই দড়িটা যতগুলো সম্ভব 3 মিটার টুকরোয় কাটো, শেষে যা বাঁচে সেটা বুদ্ধি করে জুড়ে দাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা greedy শাখার একটা **স্বাধীন গোড়া** (tracker-এ "inherited from: —") — আগের কোনো নির্দিষ্ট problem-এর সরাসরি বর্ধিত রূপ নয়। তবে এর পেছনের চিন্তার ধরনটা এই level-এর মূল সুর: **"একটা লোভী নিয়ম আন্দাজ করো, তারপর exchange argument দিয়ে প্রমাণ করো কেন সেটা সেরা।"**
এখানে exchange argument-টা হলো: "যদি কোনো সেরা সমাধানে 5-এর বড় টুকরো থাকত, আমি সেটা 3 আর বাকিটা ভেঙে গুণফল আরও বাড়াতে পারতাম — তাই সেরা সমাধানে বড় টুকরো থাকতে পারে না।" এই "ভেঙে দিলে যদি ভালো হয়, তবে আগেরটা সেরা ছিল না" যুক্তিই 103 (coin), 107 (interval) সহ এই level-এর প্রায় সব greedy-র মেরুদণ্ড। তাই এটা স্বাধীন হলেও দর্শনে পরিবারভুক্ত।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক সত্য দুটো। **এক — কখনো 4-এর বড় টুকরো রেখো না।** কারণ যেকোনো টুকরো `x ≥ 5` হলে তাকে `3 + (x−3)` ভাঙলে গুণফল বাড়ে: `3 × (x−3) ≥ x` যখন `x ≥ 5` (যেমন 5 < 3×2 = 6, 6 < 3×3 = 9)। তাই সেরা ভাঙায় সব টুকরো 2, 3 বা 4।
**দুই — 3 হলো সেরা টুকরো।** একই যোগফল পেতে 3 দিয়ে ভাঙলে গুণফল সবচেয়ে বেশি, কারণ `3 × 3 = 9 > 2 × 2 × 2 = 8` (একই যোগফল 6-এ)। আর 4-কে `2 + 2` ভাবা যায় (গুণফল একই: 4 = 2×2)। তাই নিয়ম: যতগুলো সম্ভব 3 বানাও; শেষে **remainder সামলাও** — `n % 3 == 0` হলে সব 3; remainder 1 হলে একটা 3 ভেঙে `2 + 2` করো (কারণ `3 × 1` বাজে, `2 × 2` ভালো); remainder 2 হলে শেষে একটা 2 জুড়ে দাও।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — recursion/DP দিয়ে সব ভাঙা পরীক্ষা করো। `best(x)` = `x`-কে ভেঙে পাওয়া সর্বোচ্চ গুণফল। প্রথম টুকরো `i` বাছো (1 থেকে x−1), তারপর বাকি `x − i` হয় একা থাকুক, নয় আরও ভাঙো:
```python
from functools import lru_cache
def break_brute(n):
@lru_cache(None)
def best(x):
res = 0
for i in range(1, x):
# বাকিটা একা: i*(x-i); বাকিটা আরও ভাঙা: i*best(x-i)
res = max(res, i * (x - i), i * best(x - i))
return res
return best(n)
```
এটা প্রতিটা সম্ভাবনা ছোঁয়, তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। `lru_cache`-এর কারণে O(n²)-এ চলে, ছোট/মাঝারি `n`-এ চমৎকার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
DP version O(n²) (প্রতি `x`-এর জন্য O(x) টুকরো বাছা, n-টা `x`)। `n` মাঝারি হলে ঠিক আছে, কিন্তু খুব বড় `n` (যেমন 10⁶, যদিও LeetCode-এ n ছোট) হলে এটা অপ্রয়োজনীয়ভাবে ধীর — কারণ আমরা ইতিমধ্যে গণিত থেকে **জানি** উত্তরটা শুধু 3 আর 2-এর খেলা।
```text
n = 1,000,000 হলে (কল্পনা):
DP brute : ~n^2 / 2 ≈ 5e11 ধাপ (অসম্ভব ধীর)
greedy : O(1) — শুধু n//3, n%3 আর একটা power (চোখের নিমেষে)
```
মূল অপচয় — DP প্রতিটা সম্ভাব্য টুকরো খুঁজে দেখছে, যেখানে গণিত আগেই সব সম্ভাবনা ছেঁটে দিয়ে বলে দিয়েছে "শুধু 3, সাথে remainder সামলাও"। সেই জ্ঞান কাজে লাগালে এক ধাপেই উত্তর।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — সেরা ভাঙায় শুধু **2 আর 3** টুকরো থাকে, আর 3 যত বেশি তত ভালো। তাই সরাসরি গণনা করি, DP লাগে না:
```python
def integer_break(n):
if n == 2:
return 1 # 1 + 1
if n == 3:
return 2 # 1 + 2
if n % 3 == 0:
return 3 ** (n // 3) # সব 3
if n % 3 == 1:
return 3 ** (n // 3 - 1) * 4 # একটা 3 ভেঙে 2+2 (=4)
# n % 3 == 2
return 3 ** (n // 3) * 2 # শেষে একটা 2
```
মাত্র কয়েকটা শর্ত আর একটা power — O(1) (power-এর খরচ ধরলে O(log n))। `n = 2, 3` আলাদা, কারণ সেখানে "পুরো সংখ্যা একা রাখা বারণ" নিয়মটা greedy-র সাথে সংঘর্ষে যায়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **গুণফল সর্বোচ্চ করতে সমান সমান ছোট টুকরো করো, আর সেই টুকরোর সোনালি মাপ 3-এর কাছে।**
কেন 3? দুটো যুক্তি একসাথে: (ক) 5 বা তার বড় টুকরোকে ভাঙলে গুণফল বাড়ে (`3×(x−3) ≥ x` যখন `x ≥ 5`) — তাই বড় টুকরো অপসারণযোগ্য; (খ) একই যোগফলে 3 দিয়ে ভাঙা 2 দিয়ে ভাঙার চেয়ে ভালো (`3·3 = 9 > 2·2·2 = 8`)। দুটো মিলিয়ে: সব টুকরো 3 করো, যা বাঁচে (remainder) বুদ্ধি করে সামলাও — 1 বাঁচলে একটা 3-কে 2+2 বানিয়ে শোষণ করো, 2 বাঁচলে একটা 2 জুড়ে দাও। "গুণফল সর্বোচ্চ + যোগফল স্থির" দেখলেই এই "সমান টুকরো, মাপ ≈ e ≈ 3" চিন্তাটা মাথায় আসুক।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 10`-এ কয়েকটা ভাঙা আর তাদের গুণফল পাশাপাশি দেখি:
```text
n = 10 ভাঙার কয়েক রকম:
2 + 2 + 2 + 2 + 2 -> 2·2·2·2·2 = 32
5 + 5 -> 5·5 = 25
4 + 3 + 3 -> 4·3·3 = 36 <- বড় টুকরো বাজে নয়, কিন্তু...
3 + 3 + 2 + 2 -> 3·3·2·2 = 36 <- (4 = 2+2, একই গুণফল)
3 + 3 + 4 -> 3·3·4 = 36 <- সেরা = 36
^^^^^
যতগুলো 3, বাকিটা 4 (বা 2+2)
```
remainder কীভাবে সামলাই, তিনটে কেস:
```text
n % 3 == 0: সব 3 উদাঃ 9 = 3+3+3 -> 3^3 = 27
n % 3 == 1: একটা 3 ভেঙে 2+2 উদাঃ 10 = 3+3+(2+2) -> 3^2·4 = 36
(3+1 বাজে: 3·1=3; 2+2 ভালো: 2·2=4)
n % 3 == 2: শেষে একটা 2 উদাঃ 8 = 3+3+2 -> 3^2·2 = 18
```
লক্ষ করো — remainder 1 হলে আমরা একটা 3 "ধার" নিয়ে 4 (=2+2) বানাই, কারণ একা 1 গুণফল নষ্ট করে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 10` ধরে greedy চালাই:
1. `n == 2`? না। `n == 3`? না। তাই greedy পথে।
2. `n % 3` = `10 % 3` = **1** → remainder-1 কেস।
3. সূত্র: `3 ** (n // 3 − 1) * 4` = `3 ** (10 // 3 − 1) * 4` = `3 ** (3 − 1) * 4` = `3 ** 2 * 4`।
4. হিসাব: `9 * 4` = **36**।
মানে ভাঙাটা `3 + 3 + (2 + 2)` = 10, গুণফল `3 × 3 × 2 × 2 = 36`। brute force-এর সাথে মিলে গেল।
আরেকটা: `n = 8`। `8 % 3` = 2 → remainder-2 কেস → `3 ** (8 // 3) * 2` = `3 ** 2 * 2` = `9 × 2` = **18** (ভাঙা `3 + 3 + 2`)। এটাও brute-এর সাথে মেলে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def integer_break(n):
"""n (>=2)-কে অন্তত 2 টুকরোয় ভেঙে সর্বোচ্চ গুণফল। O(log n) (power-এর খরচ)।"""
if n == 2:
return 1 # 1 + 1
if n == 3:
return 2 # 1 + 2 (পুরো 3 রাখা বারণ)
if n % 3 == 0:
return 3 ** (n // 3) # সব 3
if n % 3 == 1:
return 3 ** (n // 3 - 1) * 4 # একটা 3 ভেঙে 2+2 = 4
return 3 ** (n // 3) * 2 # n % 3 == 2: শেষে একটা 2
def break_brute(n):
"""DP দিয়ে সব ভাঙা পরীক্ষা — reference।"""
from functools import lru_cache
@lru_cache(None)
def best(x):
res = 0
for i in range(1, x):
res = max(res, i * (x - i), i * best(x - i))
return res
return best(n)
# --- হাতে বাছা test ---
assert integer_break(2) == 1
assert integer_break(3) == 2
assert integer_break(4) == 4
assert integer_break(5) == 6
assert integer_break(6) == 9
assert integer_break(7) == 12
assert integer_break(8) == 18
assert integer_break(9) == 27
assert integer_break(10) == 36
# --- brute force-এর সাথে cross-check (2 থেকে 60) ---
for n in range(2, 61):
assert integer_break(n) == break_brute(n), (n, integer_break(n), break_brute(n))
print(integer_break(10)) # 36
print(integer_break(8)) # 18
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if n == 2: return 1
if n == 3: return 2
```
ছোট দুটো ব্যতিক্রম। "অন্তত 2 টুকরো" বাধ্যবাধকতায় পুরো 2 বা 3 একা রাখা যায় না — তাই 2 → `1+1` = 1, আর 3 → `1+2` = 2। এই দুটো হাতে না সামলালে নিচের 3-সূত্র ভুল মান দিত (যেমন 3-এ `3**1 = 3`, কিন্তু পুরো 3 রাখা তো বারণ)।
```text
if n % 3 == 0: return 3 ** (n // 3)
```
`n` 3-এ নিঃশেষে ভাগ গেলে — পুরোটা 3-এর টুকরো, গুণফল `3` to the power (টুকরো সংখ্যা)।
```text
if n % 3 == 1: return 3 ** (n // 3 - 1) * 4
```
remainder 1 মানে যদি সব 3 করি, শেষে একটা 1 পড়ে থাকে — আর 1 দিয়ে গুণ গুণফল বাড়ায় না (নষ্ট)। তাই একটা 3 কমিয়ে (`n // 3 − 1` টা 3) সেই `3 + 1 = 4`-কে `2 + 2` (গুণফল 4) বানাই। `3 × 1 = 3 < 2 × 2 = 4`, তাই এটা লাভজনক।
```text
return 3 ** (n // 3) * 2
```
remainder 2 — সব 3-এর সাথে শেষে একটা 2 জুড়ি। 2-কে আর ভাঙার দরকার নেই (`2`-কে `1+1` করলে গুণফল কমে)।
cross-check অংশে 2 থেকে 60 পর্যন্ত প্রতিটা `n`-এ greedy আর DP brute মিলিয়ে দেখা — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
36
18
সব test pass!
```
প্রথম লাইন: `n=10` → dry run-এ পাওয়া 36 (`3+3+2+2`)। দ্বিতীয়: `n=8` → 18 (`3+3+2`)। তার আগের সব `assert` (হাতে বাছা 2–10 + 2 থেকে 60 পর্যন্ত DP cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — greedy সূত্র প্রতিটা কেসে নিখুঁত।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log n)** — মূল কাজ কয়েকটা তুলনা আর একটা `3 ** (n // 3)` power। Python-এ বড় সংখ্যার power-এ exponent-এর সাথে log-অনুপাতে কাজ বাড়ে, তাই O(log n)। ব্যবহারিকভাবে — DP-র O(n²)-এর তুলনায় কার্যত তাৎক্ষণিক। (ছোট মান হলে O(1) ধরাই চলে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো array, DP table বা recursion লাগছে না; শুধু গুটিকয় গণনা। (বড় সংখ্যার ফল রাখতে Python-এ সামান্য বেশি জায়গা লাগে, কিন্তু সেটা output-এর আকার, algorithm-এর বাড়তি খরচ নয়।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`n = 2` ও `n = 3` আলাদা না করা** — এই দুটোতে "পুরো সংখ্যা একা রাখা বারণ" নিয়মে greedy-সূত্র ভুল মান দেয় (3-এ 3 না, 2 চাই)। আগে এই দুটো হাতে সামলাও।
2. **remainder 1-এ একটা 3 না ভাঙা** — `3 ** (n//3) * 1` লিখলে গুণফল নষ্ট; বদলে একটা 3 কমিয়ে `× 4` করো।
3. **2 বা 4-কে আরও ভাঙা** — `2`-কে `1+1` বা `4`-কে `1+3` করলে গুণফল কমে; 2 আর 4 (=2×2) থামার জায়গা।
4. **"সমান ভাগ" ভুলে বড় টুকরো রাখা** — `5 + 5` (=25) থেকে `3+3+4` (=36) ভালো; গুণফলে সমান-ছোট টুকরোই জেতে।
5. **এটাকে "অন্তত দুই টুকরো" না ভাবা** — কোনো কোনো variant-এ পুরো `n` একা রাখা যায় (তখন উত্তর n); এখানে যায় না — শর্ত মন দিয়ে পড়ো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Integer Break** (