Skip to content

018 — Sum of Two Values

Source

  • Original source: Classic complement-lookup exercise (CP scale)
  • Platform: CSES — https://cses.fi/problemset/ (task name: Sum of Two Values)
  • Topic: hash map (complement lookup)
  • Difficulty: Medium
  • Pattern: complement lookup
  • Basic idea inherited from: CP input size-এ Two Sum — একই tweak, কিন্তু বড় n আর 1-indexed উত্তর

1. Problem in simple words

nটা সংখ্যা আর একটা target x দেওয়া আছে। এমন দুটো ভিন্ন position খুঁজে বের করতে হবে যাদের সংখ্যা দুটো যোগ করলে ঠিক x হয়, আর সেই দুটো position ছাপতে হবে। CSES-এর নিয়মে position 1 থেকে গোনা (1-indexed)। কোনো জোড়া না থাকলে IMPOSSIBLE ছাপতে হয়।

nums = [2, 7, 5, 1], x = 9   (1-indexed)
2 + 7 = 9  →  position 1 ও 2
উত্তর: 1 2

2. Which basic idea does this inherit from?

এটা হুবহু Two Sum (#1)-এর complement lookup — শুধু পোশাক বদলেছে। দুটো পার্থক্য: (১) CSES competitive scale-এ n অনেক বড় হতে পারে (10^5+), তাই O(n^2) একদম চলবে না, hash map লাগবেই; (২) উত্তর হলো 1-indexed position, array index নয়। ../patterns.md-তে এটা Pattern 2।

3. What is the hidden math or logic?

সেই একই সরল বীজগণিত: দুটো সংখ্যা a + b = x চাই, তাই হাতে থাকা v-এর জন্য দরকারি partner একটাই — x - v (complement)। প্রশ্নটা বদলে যায় "এই নির্দিষ্ট complement কি আগে কোনো position-এ দেখেছি?"-তে। যেহেতু আমরা position ফেরত দিচ্ছি, map-এ মান হিসেবে value-র position রাখতে হবে।

4. Which data structure is needed?

একটা hash map (value → 1-indexed position)। শুধু "complement আছে কি না" জানলে হবে না — তার position-টাও দরকার, কারণ আমরা index ছাপছি। CP-তে Python-এর dict যথেষ্ট দ্রুত।

5. Why this data structure fits

need in seen membership-check গড়ে O(1), পুরো scan O(n)। n = 2·10^5-এ O(n^2) মানে ৪০ বিলিয়ন অপারেশন — time limit-এ অসম্ভব; hash map সেটাকে রৈখিক করে দেয়। সাথে map প্রতিটা value-র প্রথম position ধরে রাখে, ঠিক যা ছাপতে হবে।

6. Real-life analogy

ভাবো একটা বড় হলঘরে অনেক লোক, প্রত্যেকের গায়ে একটা নম্বর-ব্যাজ। তুমি এমন জোড়া খুঁজছ যাদের নম্বরের যোগ ঠিক x। তুমি সবার সাথে সবাইকে মেলাও না — নতুন একজন এলে শুধু ভাবো "x পেতে হলে এর partner-এর নম্বর কত? আগে কি সেই নম্বরের কাউকে দেখেছি, আর কোথায় দাঁড়িয়ে ছিল?" তোমার মাথার সেই "নম্বর → কে কোথায়" তালিকাটাই hash map।

7. Visual explanation

nums = [2, 7, 5, 1], x = 9। seen (value → 1-indexed position) ভরে; প্রতি ধাপে need = x - v খুঁজি:

pos=1 v=2  need=9-2=7  7 in {}?            না   → seen={2:1}
pos=2 v=7  need=9-7=2  2 in {2:1}?         হ্যাঁ → উত্তর (seen[2], 2) = (1, 2)

partner-কে সামনে খুঁজি না — শুধু পেছনের স্মৃতিতে তাকাই, তাই ছোট position সবসময় আগে আসে।

8. Example input and output

Input : nums = [2, 7, 5, 1],     x = 9     Output: 1 2
Input : nums = [1, 4, 5, 3, 11],  x = 9     Output: 2 3   (4 + 5)
Input : nums = [1, 2, 3],         x = 100   Output: IMPOSSIBLE
Input : nums = [5, 5],            x = 10     Output: 1 2   (একই value, ভিন্ন position)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা জোড়া position (i, j) ধরে দেখি যোগফল x কি না।

প্রতিটা i-র জন্য:
    প্রতিটা j > i-র জন্য:
        nums[i] + nums[j] == x হলে print(i+1, j+1)   # 1-indexed
কিছু না পেলে print("IMPOSSIBLE")

10. Why brute force is slow

দুটো nested loop মানে O(n^2)। ছোট LeetCode input-এ চলে গেলেও CSES-এর বড় n-এ time limit ফেটে যাবে। অপচয়টা Two Sum-এর মতোই: প্রতিটা সংখ্যার জন্য আমরা বাকি পুরো array আবার scan করছি, যদিও ঠিক জানি কোন একটাই সংখ্যা (x - v) দরকার। জানা জিনিস খুঁজতে scan লাগে না।

11. Key observation

মূল observation: partner অনুমান নয়, হিসেব করা যায় — x - v। তাই কাজটা "একটা নির্দিষ্ট value আগে কোন position-এ এসেছিল?" দেখায় নেমে আসে, যা hash map গড়ে O(1)-এ বলে। বড় n-এ এটাই একমাত্র বাঁচার পথ।

12. Optimized intuition

array-র উপর একবারই হাঁটো, position 1 থেকে গোনা। প্রতিটা v-তে জিজ্ঞেস করো "x - v কি seen-এ আছে?" — থাকলে জোড়া পেয়ে গেছ, দুটো position ফেরত দাও (আগের + এখনকার)। না থাকলে নিজেকে (v → এখনকার position) seen-এ রেখে এগোও। এক pass, O(n)।

13. Thinking tweak

মোচড়: জোড়া খুঁজো না — এ পর্যন্ত কী দেখেছ, কোথায় দেখেছ, সেটা মনে রাখো। এটি Two Sum-এরই tweak ("search না করে remember করো"), শুধু এখানে index-এর বদলে 1-indexed position টুকে রাখছি। CP-তে এই tweak আয়ত্তে থাকলে অনেক "pair with sum/diff" problem তাৎক্ষণিক সমাধান হয়।

14. Step-by-step dry run

Input nums = [1, 4, 5, 3, 11], x = 9:

  1. শুরু: seen = {} (খালি)।
  2. pos=1, v=1: need = 8; 8 in {}? না → seen = {1: 1}।
  3. pos=2, v=4: need = 5; 5 in {1:1}? না → seen = {1:1, 4:2}।
  4. pos=3, v=5: need = 4; 4 in seen? হ্যাঁ (position 2) → উত্তর (2, 3)।
  5. শেষ: 4 + 5 = 9, position 2 ও 3।

15. Python solution

def sum_of_two_values(nums, x):
    seen = {}                              # value -> 1-indexed position
    for i, v in enumerate(nums, start=1):  # CSES position 1 থেকে গোনে
        need = x - v                       # partner হিসেব করো
        if need in seen:                   # অতীত কি partner দিয়েছে?
            return (seen[need], i)         # ছোট position আগে (need আগে দেখা)
        seen[v] = i                        # নিজেকে position সহ মনে রাখো
    return None                            # কোনো জোড়া নেই → "IMPOSSIBLE"

# ---- tests ----
assert sum_of_two_values([2, 7, 5, 1], 9) == (1, 2)
assert sum_of_two_values([1, 4, 5, 3, 11], 9) == (2, 3)   # 4 + 5
assert sum_of_two_values([1, 2, 3], 100) is None          # IMPOSSIBLE
assert sum_of_two_values([5, 5], 10) == (1, 2)            # একই value, ভিন্ন position
print("সব test pass!")

16. Line-by-line code explanation

  • seen = {} — খালি hash map, value → প্রথম যে position-এ দেখা।
  • enumerate(nums, start=1) — position 1 থেকে গোনা শুরু, কারণ CSES 1-indexed উত্তর চায়।
  • need = x - v — v-এর জন্য দরকারি partner হিসেব।
  • if need in seen — সেই partner কি আগে দেখেছি? dict-এ গড়ে O(1)।
  • return (seen[need], i) — পেলে partner-এর আগের position আর এখনকার position; আগেরটা ছোট, তাই আগে।
  • seen[v] = i — না পেলে নিজেকে position সহ টুকে রাখি, যাতে পরে কেউ partner হিসেবে পায়।
  • return None — loop শেষেও জোড়া না মিললে; বাস্তব submission-এ এখানে IMPOSSIBLE ছাপা হতো।

17. Output walkthrough

[2,7,5,1] x=9-এ position 1-এ 2 যায় seen-এ; position 2-এ v=7, need=2, যা seen-এ আছে → (1, 2)। [1,4,5,3,11]-এ জোড়া হয় position 2 ও 3 (4+5) → (2, 3)। [1,2,3] x=100-এ কোনো partner মেলে না → None (অর্থাৎ IMPOSSIBLE)। [5,5]-এ দ্বিতীয় 5-এর complement 5 আগে position 1-এ দেখা → (1, 2)। শেষে print: সব test pass!।

18. Time complexity

O(n) — array-র উপর একবারই হাঁটি, প্রতি element-এ hash map operation গড়ে O(1)। বড় CSES input-এ এটাই গ্রহণযোগ্য।

19. Space complexity

O(n) — worst case-এ প্রায় সব value seen map-এ জমতে পারে।

20. Common mistakes

  • 0-indexed ফেরত দেওয়া — CSES 1-indexed চায়; enumerate(..., start=1) ব্যবহার না করলে উত্তর এক ঘর কম হয়ে wrong answer।
  • lookup-এর আগে insert করা — seen[v] = i আগে করলে x জোড় হলে একই element নিজের সাথে জোড়া বানিয়ে এক position দুবার দেয়; সবসময় আগে check, পরে insert।
  • O(n^2) brute force দিয়ে চেষ্টা করা — CSES-এর বড় n-এ time limit exceed; hash map বাধ্যতামূলক।

21. Which basic problem this inherits from

ভিত্তি: Two Sum (#1)-এর complement lookup। এই note দেখায় একই pattern কীভাবে competitive scale-এ (বড় n, 1-indexed I/O) প্রয়োগ হয় — algorithm এক, শুধু input-আকার আর output-ফরম্যাট বদলায়। সম্পূর্ণ চাল ../patterns.md-র Pattern 2-এ (CSES "Sum of Two Values" উদাহরণসহ উল্লেখিত)।

22. Similar harder problems

23. Pattern learned

Complement lookup (CP scale): partner হিসেব করো (x - v), তারপর "search না করে remember করো" — value → position টুকে রাখো, এক pass, O(1) lookup। বড় n-এ O(n^2) বাদ, hash map বাধ্যতামূলক; উত্তর 1-indexed।

24. Final summary

ভবিষ্যতের আমাকে: CP-তে "pair with sum x, positions ছাপো" দেখলেই Two Sum-এর hand-reflex — partner = x - v, প্রশ্ন ঘুরিয়ে "আগে দেখেছি কোথায়?"। শুধু দুটো জিনিস আলাদা: position 1 থেকে গোনা, আর জোড়া না থাকলে IMPOSSIBLE। algorithm সেই চেনা one-pass hash map।

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