Skip to content

110 — Maximum Product by Splitting (Integer Break)

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

Source

  • 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: — (এই শাখার স্বাধীন গোড়া)

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

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 জুড়ে দাও।

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-র মেরুদণ্ড। তাই এটা স্বাধীন হলেও দর্শনে পরিবারভুক্ত।

4. Real-life analogy

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

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

5. Visual explanation

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 গুণফল নষ্ট করে।

6. Example input and 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 করতে হয়।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — recursion/DP দিয়ে সব ভাঙা পরীক্ষা করো। best(x) = x-কে ভেঙে পাওয়া সর্বোচ্চ গুণফল। প্রথম টুকরো i বাছো (1 থেকে x−1), তারপর বাকি x − i হয় একা থাকুক, নয় আরও ভাঙো:

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-এর খেলা।

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 লাগে না:

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" চিন্তাটা মাথায় আসুক।

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-এর সাথে মেলে।

12. Python solution

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

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!।

14. Output walkthrough

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

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

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); এখানে যায় না — শর্ত মন দিয়ে পড়ো।

18. Harder problems that inherit this idea

19. Pattern learned

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 দিয়ে প্রমাণিত।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।