110 — Maximum Product by Splitting (Integer Break)¶

এই problem-টা greedy-র একটা দারুণ মজার দিক দেখায় — উত্তরটা শুনলে অবাক লাগে: "সংখ্যাটাকে যতগুলো 3-এ ভাঙা যায় ভাঙো!" কেন 3? কেন 2 নয়, 4 নয়? এই "কেন"-টার একটা ছোট্ট সুন্দর প্রমাণ আছে, আর সেই প্রমাণ বোঝাই এই note-এর হৃদপিণ্ড। মনে রেখো — এই level-এ greedy কেন কাজ করে সেটা না বুঝে এগিও না।

Problem link ও উৎস

Original source: LeetCode — Integer Break
Platform: LeetCode — https://leetcode.com/problems/integer-break/
Topic: Math-based programming fundamentals → Level 8: Greedy Math Tricks
Difficulty: Medium
Pattern: break into 3s (সংখ্যাকে যথাসম্ভব 3-এর টুকরোয় ভাগ করা)
Basic idea inherited from: — (এই শাখার স্বাধীন গোড়া)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা ধনাত্মক পূর্ণসংখ্যা 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¶

উদাহরণ

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 করতে হয়।

চেনা উদাহরণে বোঝা¶

ভাবো তোমার হাতে n মিটার লম্বা একটা দড়ি, আর তুমি সেটা কয়েক টুকরো করে কাটবে। প্রতিটা টুকরো দিয়ে একটা করে বর্গাকার বেড়া বানাবে, আর তোমার "স্কোর" = সব বেড়ার ক্ষেত্রফলের গুণফল। কীভাবে কাটলে স্কোর সর্বোচ্চ?

খুব ছোট টুকরো (1 মিটার) বাজে — গুণফলে 1 দিয়ে গুণ করলে কিছুই বাড়ে না, বরং দড়ি নষ্ট। খুব বড় টুকরোও বাজে — একটা বড় টুকরোকে দুই-তিন টুকরো করলে গুণফল বাড়ে (কারণ গুণ যোগের চেয়ে দ্রুত বাড়ে)। মাঝামাঝি একটা "সোনালি মাপ" আছে — সেটা 3-এর কাছাকাছি (গণিতে আসল সর্বোত্তম e ≈ 2.718, পূর্ণসংখ্যায় তার নিকটতম 3)। তাই দড়িটা যতগুলো সম্ভব 3 মিটার টুকরোয় কাটো, শেষে যা বাঁচে সেটা বুদ্ধি করে জুড়ে দাও।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এটা greedy শাখার একটা স্বাধীন গোড়া (tracker-এ "inherited from: —") — আগের কোনো নির্দিষ্ট problem-এর সরাসরি বর্ধিত রূপ নয়। তবে এর পেছনের চিন্তার ধরনটা এই level-এর মূল সুর: "একটা লোভী নিয়ম আন্দাজ করো, তারপর exchange argument দিয়ে প্রমাণ করো কেন সেটা সেরা।"

এখানে exchange argument-টা হলো: "যদি কোনো সেরা সমাধানে 5-এর বড় টুকরো থাকত, আমি সেটা 3 আর বাকিটা ভেঙে গুণফল আরও বাড়াতে পারতাম — তাই সেরা সমাধানে বড় টুকরো থাকতে পারে না।" এই "ভেঙে দিলে যদি ভালো হয়, তবে আগেরটা সেরা ছিল না" যুক্তিই 103 (coin), 107 (interval) সহ এই level-এর প্রায় সব greedy-র মেরুদণ্ড। তাই এটা স্বাধীন হলেও দর্শনে পরিবারভুক্ত।

ভেতরের অঙ্ক¶

মূল গাণিতিক সত্য দুটো। এক — কখনো 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 জুড়ে দাও।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

সবচেয়ে সরল চিন্তা — 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-এ চমৎকার।

কোথায় বেশি কাজ হতে পারে¶

DP version O(n²) (প্রতি x-এর জন্য O(x) টুকরো বাছা, n-টা x)। n মাঝারি হলে ঠিক আছে, কিন্তু খুব বড় n (যেমন 10⁶, যদিও LeetCode-এ n ছোট) হলে এটা অপ্রয়োজনীয়ভাবে ধীর — কারণ আমরা ইতিমধ্যে গণিত থেকে জানি উত্তরটা শুধু 3 আর 2-এর খেলা।

উদাহরণ

n = 1,000,000 হলে (কল্পনা):
  DP brute : ~n^2 / 2 ≈ 5e11 ধাপ   (অসম্ভব ধীর)
  greedy   : O(1) — শুধু n//3, n%3 আর একটা power   (চোখের নিমেষে)

মূল অপচয় — DP প্রতিটা সম্ভাব্য টুকরো খুঁজে দেখছে, যেখানে গণিত আগেই সব সম্ভাবনা ছেঁটে দিয়ে বলে দিয়েছে "শুধু 3, সাথে remainder সামলাও"। সেই জ্ঞান কাজে লাগালে এক ধাপেই উত্তর।

আরও ভালোভাবে ভাবা¶

মূল 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-র সাথে সংঘর্ষে যায়।

ভাবনার পরিবর্তন¶

আসল "আহা!" — গুণফল সর্বোচ্চ করতে সমান সমান ছোট টুকরো করো, আর সেই টুকরোর সোনালি মাপ 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" চিন্তাটা মাথায় আসুক।

ছবিতে বোঝা¶

n = 10-এ কয়েকটা ভাঙা আর তাদের গুণফল পাশাপাশি দেখি:

উদাহরণ

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 কীভাবে সামলাই, তিনটে কেস:

উদাহরণ

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-এ ধাপে ধাপে¶

n = 10 ধরে greedy চালাই:

n == 2? না। n == 3? না। তাই greedy পথে।
n % 3 = 10 % 3 = 1 → remainder-1 কেস।
সূত্র: 3 ** (n // 3 − 1) * 4 = 3 ** (10 // 3 − 1) * 4 = 3 ** (3 − 1) * 4 = 3 ** 2 * 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-এর সাথে মেলে।

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

উদাহরণ

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 রাখা তো বারণ)।

উদাহরণ

if n % 3 == 0: return 3 ** (n // 3)

n 3-এ নিঃশেষে ভাগ গেলে — পুরোটা 3-এর টুকরো, গুণফল 3 to the power (টুকরো সংখ্যা)।

উদাহরণ

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, তাই এটা লাভজনক।

উদাহরণ

return 3 ** (n // 3) * 2

remainder 2 — সব 3-এর সাথে শেষে একটা 2 জুড়ি। 2-কে আর ভাঙার দরকার নেই (2-কে 1+1 করলে গুণফল কমে)।

cross-check অংশে 2 থেকে 60 পর্যন্ত প্রতিটা n-এ greedy আর DP brute মিলিয়ে দেখা — সব মিললে সব test pass!।

Output মিলিয়ে দেখা¶

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

উদাহরণ

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 সূত্র প্রতিটা কেসে নিখুঁত।

খরচ ও সাধারণ ভুল¶

সময়¶

O(log n) — মূল কাজ কয়েকটা তুলনা আর একটা 3 ** (n // 3) power। Python-এ বড় সংখ্যার power-এ exponent-এর সাথে log-অনুপাতে কাজ বাড়ে, তাই O(log n)। ব্যবহারিকভাবে — DP-র O(n²)-এর তুলনায় কার্যত তাৎক্ষণিক। (ছোট মান হলে O(1) ধরাই চলে।)

অতিরিক্ত জায়গা¶

O(1) — কোনো array, DP table বা recursion লাগছে না; শুধু গুটিকয় গণনা। (বড় সংখ্যার ফল রাখতে Python-এ সামান্য বেশি জায়গা লাগে, কিন্তু সেটা output-এর আকার, algorithm-এর বাড়তি খরচ নয়।)

যে ভুলগুলো এড়াতে হবে¶

n = 2 ও n = 3 আলাদা না করা — এই দুটোতে "পুরো সংখ্যা একা রাখা বারণ" নিয়মে greedy-সূত্র ভুল মান দেয় (3-এ 3 না, 2 চাই)। আগে এই দুটো হাতে সামলাও।
remainder 1-এ একটা 3 না ভাঙা — 3 ** (n//3) * 1 লিখলে গুণফল নষ্ট; বদলে একটা 3 কমিয়ে × 4 করো।
2 বা 4-কে আরও ভাঙা — 2-কে 1+1 বা 4-কে 1+3 করলে গুণফল কমে; 2 আর 4 (=2×2) থামার জায়গা।
"সমান ভাগ" ভুলে বড় টুকরো রাখা — 5 + 5 (=25) থেকে 3+3+4 (=36) ভালো; গুণফলে সমান-ছোট টুকরোই জেতে।
এটাকে "অন্তত দুই টুকরো" না ভাবা — কোনো কোনো variant-এ পুরো n একা রাখা যায় (তখন উত্তর n); এখানে যায় না — শর্ত মন দিয়ে পড়ো।

শেখা ও পরের অনুশীলন¶

এই ধারণার পরের অনুশীলন¶

LeetCode — Integer Break (https://leetcode.com/problems/integer-break/) — এটাই মূল problem; এখানে greedy ও DP দুই রাস্তাই দেখা হলো।
LeetCode — Maximum Product of Splitted Binary Tree (https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/) — ভিন্ন কাঠামো (tree), কিন্তু "ভাগ করে গুণফল সর্বোচ্চ" একই সুর।
LeetCode — Maximum Score After Splitting a String (https://leetcode.com/problems/maximum-score-after-splitting-a-string/) — "কোথায় ভাঙলে সেরা" — splitting + optimize চিন্তার আত্মীয়।

কৌশলটি মনে রাখুন¶

Greedy splitting into equal small parts (break into 3s) — যোগফল স্থির রেখে গুণফল সর্বোচ্চ করতে সমান-ছোট টুকরো করো, পূর্ণসংখ্যায় সেরা মাপ 3; remainder 1 → একটা 3 ভেঙে 2+2, remainder 2 → শেষে একটা 2। বড় শিক্ষা: "যোগফল স্থির, গুণফল max" = সমান ভাগ; আর সেই সমান ভাগের সেরা মাপ e ≈ 2.718-এর নিকটতম পূর্ণসংখ্যা, অর্থাৎ 3 — exchange argument দিয়ে প্রমাণিত।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে এক লাইনে: "Integer Break = যতগুলো সম্ভব 3-এ ভাঙো; n%3==0 → 3^(n/3), %3==1 → 3^(n/3−1)·4, %3==2 → 3^(n/3)·2; n=2→1, n=3→2 আলাদা। Signal: 'যোগফল স্থির রেখে গুণফল max' দেখলেই '3-এ ভাঙো' মনে পড়ুক — কারণ 3·3 > 2·2·2 আর বড় টুকরো ভাঙলেই লাভ।"

পরের ধাপ → 111 — Make Array Equal with Minimum Moves (আরেক greedy math মোচড় — median target)। সম্পর্কিত → 103 — Minimum Coins Basic (greedy কখন fail করে, তার সাবধানবাণী)।

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

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