Skip to content

010 — Add Two Numbers

Source

  • Original source: Classic linked list exercise
  • Platform: LeetCode — https://leetcode.com/problems/add-two-numbers/
  • Topic: linked list
  • Difficulty: Medium
  • Pattern: dummy head + carry
  • Basic idea inherited from: merge skeleton (problem 2) + স্কুলের হাতে-যোগ (math fundamentals)

1. Problem in simple words

দুটো সংখ্যা দুটো linked list হিসেবে দেওয়া, কিন্তু digit গুলো উল্টো করে রাখা — মানে একক স্থানের digit সবার আগে। দুটো সংখ্যা যোগ করে ফলটাও একই রকম উল্টো-digit list হিসেবে return করো।

342 লেখা আছে :  2 -> 4 -> 3      (একক আগে: 2, তারপর 4, তারপর 3)
465 লেখা আছে :  5 -> 6 -> 4
342 + 465 = 807
ফল         :  7 -> 0 -> 8

2. Which basic idea does this inherit from?

দুটো জিনিস জোড়া লাগছে। প্রথমত problem 2 (002-merge-two-sorted-lists.md)-এর dummy + tail কাঠামো — দুটো list একসাথে হেঁটে নতুন list বানানো। দ্বিতীয়ত স্কুলে শেখা হাতে-যোগ: ডান থেকে digit যোগ করো, ১০ পেরোলে "হাতে এক" (carry) পরের ঘরে নাও। digit উল্টো থাকায় list-এর শুরু থেকেই হাঁটা মানে একক স্থান থেকে শুরু — যোগের জন্য একদম উপযুক্ত।

3. What is the hidden math or logic?

লুকানো অঙ্ক positional addition। প্রতি ঘরে: sum = d1 + d2 + carry; নতুন digit হলো sum % 10, আর পরের ঘরের carry হলো sum // 10। Python-এ divmod(sum, 10) একবারে (carry, digit) দিয়ে দেয়। উল্টো-digit রাখায় index অনুযায়ী জায়গা মেলানো লাগে না — দুই list সমানতালে এগোলেই হয়।

4. Which data structure is needed?

একটা dummy head + একটা tail pointer (ফল গাঁথতে), আর একটা carry সংখ্যা। নতুন প্রতিটা digit-এর জন্য নতুন node বানিয়ে tail-এ জুড়ি।

5. Why this data structure fits

Linked list-এ শেষে node জোড়া O(1) (tail ধরে রাখলে), আর দৈর্ঘ্য আগে জানার দরকার নেই — যোগ যতদূর গড়ায় ততদূর জোড়া যায়। dummy head থাকায় ফল-list-এর প্রথম node নিয়ে আলাদা ভাবতে হয় না; carry শেষ পর্যন্ত থাকলে এক ঘর বেড়ে যাওয়া সংখ্যাও (যেমন 99 + 1 = 100) সহজে ধরা পড়ে।

6. Real-life analogy

হাতে কলমে দুটো সংখ্যা যোগ করার মতো — ডান দিক (একক) থেকে শুরু করো, প্রতি কলামে যোগ করো, ১০ বা তার বেশি হলে নিচে এক ঘরের digit লেখো আর "এক হাতে" পরের কলামে নিয়ে যাও। list-এর উল্টো-digit মানে তুমি এমনিতেই ডান দিক থেকে শুরু করছ।

7. Visual explanation

carry সহ ঘরে ঘরে যোগ। 2->4->3 (342) আর 5->6->4 (465):

ঘর 1:  2 + 5 + carry(0) = 7  → digit 7, carry 0   ফল: 7
ঘর 2:  4 + 6 + carry(0) = 10 → digit 0, carry 1   ফল: 7 -> 0
ঘর 3:  3 + 4 + carry(1) = 8  → digit 8, carry 0   ফল: 7 -> 0 -> 8
দুই list শেষ, carry 0 → থামো

return: 7 -> 0 -> 8   (= 807)

8. Example input and output

Input : l1 = 2 -> 4 -> 3 , l2 = 5 -> 6 -> 4   -> Output: 7 -> 0 -> 8   (342+465=807)

Edge 1 (শেষে carry বাকি): l1 = 9 -> 9 , l2 = 1     -> Output: 0 -> 0 -> 1   (99+1=100)
Edge 2 (অসমান দৈর্ঘ্য)  : l1 = 0 , l2 = 0          -> Output: 0
Edge 3 (একটা লম্বা)     : l1 = 5 , l2 = 5          -> Output: 0 -> 1   (5+5=10)

9. Brute force thinking

সরল চিন্তা: দুই list-কে আলাদা করে পূর্ণ সংখ্যায় রূপান্তর করো (digit গুলো বসিয়ে), Python-এ যোগ করো, তারপর ফলের digit গুলো আবার উল্টো করে list বানাও।

2->4->3  =>  342
5->6->4  =>  465
342 + 465 = 807
807 => 7 -> 0 -> 8

10. Why brute force is slow

এটা ছোট input-এ কাজ করে, কিন্তু সংখ্যা বিশাল হলে (হাজার হাজার digit) পুরো সংখ্যা বানিয়ে যোগ করা ভঙ্গুর ও অপচয় — অনেক ভাষায় তো বড় সংখ্যাই ধরবে না। ঘরে-ঘরে carry পদ্ধতি কোনো বড় সংখ্যা না বানিয়ে এক পাসেই কাজ সারে, যেকোনো দৈর্ঘ্যে।

11. Key observation

মূল observation: পুরো সংখ্যা বানানোর দরকার নেই। প্রতিটা ঘর স্বাধীনভাবে যোগ করা যায়, শুধু এক ঘরের carry পরের ঘরে নিয়ে গেলেই হয়। উল্টো-digit থাকায় দুই list সমানে এগোলেই ঘর গুলো মিলে যায়।

12. Optimized intuition

dummy + tail বানাও, carry = 0 রাখো। যতক্ষণ l1 বা l2-এ node আছে অথবা carry বাকি আছে: দুই (থাকলে) digit আর carry যোগ করো, divmod(sum, 10) দিয়ে নতুন carry ও digit বের করো, digit-এর node tail-এ জুড়ো, দুই list (থাকলে) এগোও। শেষে dummy.next।

13. Thinking tweak

মোচড়: "দুটো সংখ্যা যোগ" না ভেবে ভাবো — "দুটো digit-স্রোত একসাথে হাঁটাই, প্রতি ঘরে যোগ + হাতে-এক বহন করি।" loop শর্তে carry-কেও রাখলে শেষের অতিরিক্ত digit (100-এর সেই 1) আপনাআপনি ধরা পড়ে।

14. Step-by-step dry run

Input l1 = 9 -> 9, l2 = 1 (99 + 1 = 100):

  1. dummy, tail = dummy, carry = 0
  2. ঘর 1: 9 + 1 + 0 = 10 → divmod(10,10) = (1, 0) → node 0; carry = 1; l1 = 9, l2 = None
  3. ঘর 2: 9 + 0 + 1 = 10 → (1, 0) → node 0; carry = 1; l1 = None
  4. ঘর 3: l1/l2 শেষ, কিন্তু carry = 1 → 0 + 0 + 1 = 1 → (0, 1) → node 1; carry = 0
  5. সব শেষ, carry 0 → থামো; return dummy.next = 0 -> 0 -> 1 (= 100)

15. Python solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers(l1, l2):
    dummy = ListNode()        # নকল head — ফলের প্রথম node-এর special case এড়াতে
    tail = dummy
    carry = 0
    while l1 or l2 or carry:  # carry-ও শর্তে: শেষের অতিরিক্ত digit ধরতে
        s = carry
        if l1:
            s += l1.val
            l1 = l1.next
        if l2:
            s += l2.val
            l2 = l2.next
        carry, digit = divmod(s, 10)   # (হাতে-এক, এই ঘরের digit)
        tail.next = ListNode(digit)
        tail = tail.next
    return dummy.next

# ---- helpers (test-এর জন্য) ----
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

# ---- tests ----
assert to_list(add_two_numbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8]  # 342+465
assert to_list(add_two_numbers(build([9, 9]), build([1]))) == [0, 0, 1]           # 99+1
assert to_list(add_two_numbers(build([0]), build([0]))) == [0]                    # 0+0
assert to_list(add_two_numbers(build([5]), build([5]))) == [0, 1]                 # 5+5=10
print("সব test pass!")

16. Line-by-line code explanation

  • dummy = ListNode() — নকল head, ফল-list সহজে গাঁথতে।
  • tail = dummy — tail সবসময় ফল-list-এর শেষে।
  • carry = 0 — শুরুতে হাতে কিছু নেই।
  • while l1 or l2 or carry: — যেকোনো list বাকি থাকলে, বা carry বাকি থাকলে চলবে।
  • s = carry তারপর if l1: ... if l2: ... — যেটা যেটা আছে যোগ করো, সেই list এগোও।
  • carry, digit = divmod(s, 10) — পরের carry আর এই ঘরের digit একসাথে।
  • tail.next = ListNode(digit); tail = tail.next — নতুন digit-node জুড়ে tail এগোও।
  • return dummy.next — ফলের আসল head।

17. Output walkthrough

[2,4,3] + [5,6,4] ঘরে-ঘরে 7,0,8 দেয় → [7,0,8]। [9,9] + [1]-এ carry শেষ পর্যন্ত গড়িয়ে [0,0,1]। [0] + [0] → [0]। [5] + [5]-এ 10 → [0,1]। সব assert pass → সব test pass!।

18. Time complexity

O(max(n, m)) — n, m দুই list-এর দৈর্ঘ্য; লম্বাটার প্রতিটা ঘর একবার করে process হয় (+ সম্ভবত একটা অতিরিক্ত carry ঘর)।

19. Space complexity

O(max(n, m)) — ফল-list-এ ততগুলো নতুন node বানে; pointer ছাড়া অন্য কোনো বড় structure নেই। (output বাদ দিলে auxiliary O(1)।)

20. Common mistakes

  • loop শর্তে carry রাখতে ভুলে যাওয়া — তখন শেষের অতিরিক্ত digit (যেমন 100-এর 1) হারিয়ে যায়।
  • l1/l2 None কিনা না দেখে .val পড়া — অসমান দৈর্ঘ্যে crash।
  • carry আর digit উল্টে নেওয়া (digit, carry = divmod(...)) — divmod ফেরায় (ভাগফল, ভাগশেষ), তাই carry আগে।

21. Which basic problem this inherits from

ভিত্তি: problem 2 (002-merge-two-sorted-lists.md)-এর dummy + tail দিয়ে দুই list একসাথে হাঁটার skeleton; সাথে স্কুলের positional addition (math fundamentals)।

22. Similar harder problems

23. Pattern learned

Dummy head + carry: দুটো digit-স্রোত একসাথে হাঁটিয়ে, প্রতি ঘরে যোগ ও carry বহন করে নতুন list গাঁথা; loop শর্তে carry রাখলে শেষের অতিরিক্ত digit আপনাআপনি আসে।

24. Final summary

ভবিষ্যতের আমাকে: "list হিসেবে রাখা সংখ্যা যোগ করতে হলে — পুরো সংখ্যা বানিও না, ঘরে-ঘরে divmod(d1+d2+carry, 10) চালাও, dummy+tail-এ গাঁথো, loop শর্তে carry রাখো।" উল্টো-digit মানেই ঘর সমানে মেলে।

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