धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग
लक्ष्य-योग असाइनमेंट समस्या को उपसमुच्चय-योग अंतर वाले नैपसैक में बदलिए और इसे O(n × sum) समय में हल कीजिए।
धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
लक्ष्य योग की समस्या
एक पूर्णांक सरणी nums और एक पूर्णांक target दिए गए हैं। प्रत्येक संख्या को + या - चिह्न दें, ताकि परिणामी व्यंजक का मान target हो। ऐसा करने के अलग-अलग तरीकों की संख्या लौटाएँ। उदाहरण के लिए, nums=[1,1,1,1,1] और target=3 के लिए 5 तरीके हैं (अलग-अलग स्थानों पर 4 तत्वों को धनात्मक और 1 तत्व को ऋणात्मक चुनकर)।
बलपूर्वक प्रयास: DFS गणना
DFS विधि प्रत्येक संख्या को + या - देती है और पुनरावर्ती रूप से आगे बढ़ती है; यह उन पत्ती-नोडों की संख्या लौटाती है जिनका योग target तक पहुँचता है। यह सही है, लेकिन इसकी O(2^n) समय जटिलता — घातांकीय — है। n=20 के लिए यह दस लाख से अधिक पुनरावर्ती कॉल है। पहले DFS विधि का उल्लेख करना और फिर शीघ्र ही DP अनुकूलन की ओर बढ़ना उपयोगी है।
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5मेमोकरणयुक्त DFS
DFS में मेमोकरण जोड़ें: स्थिति (index, current_sum) है। चूँकि current_sum -total से +total तक हो सकता है, इसलिए O(n × total) विशिष्ट स्थितियाँ हैं। मेमोकरण के साथ DFS O(n × total) समय और स्थान में चलता है। यह विधि काम करती है और साक्षात्कार में मान्य है, लेकिन रूपांतरण-आधारित DP अधिक सुंदर और स्थान-कुशल है।
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5गणितीय रूपांतरण
मान लें कि P उन संख्याओं का समुच्चय है जिन्हें + दिया गया है और N उन संख्याओं का समुच्चय है जिन्हें - दिया गया है। तब: sum(P) - sum(N) = target और sum(P) + sum(N) = total। दोनों समीकरण जोड़ने पर: 2 × sum(P) = target + total, इसलिए sum(P) = (target + total) / 2। समस्या बदलकर यह हो जाती है: (target + total) / 2 योग वाले nums के उपसमुच्चयों की संख्या गिनना। यह 0/1 नैपसैक के उपसमुच्चयों की गिनती वाले रूप के बिल्कुल समान है।
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')DP से पहले वैधता जाँचें
DP चलाने से पहले जाँचें: (1) target + total सम होना चाहिए (अन्यथा sum(P) पूर्णांक नहीं होगा — इसलिए समस्या असंभव है); (2) abs(target) > total का अर्थ है कि सभी चिह्न एक ही दिशा में होने पर भी लक्ष्य प्राप्त नहीं किया जा सकता। इनमें से कोई जाँच विफल हो तो तुरंत 0 लौटाएँ। ये जाँचें DP लूप के भीतर विशेष स्थितियों को अलग से संभालने के बिना सीमांत स्थितियों को साफ़-सुथरे ढंग से संभालती हैं।
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5छोटे उदाहरण का चरण-दर-चरण अनुशीलन
nums=[1,1,1,1,1] और target=3 के लिए: कुल=5, new_target=(3+5)//2=4। हम [1,1,1,1,1] में से 4 योग वाले उपसमुच्चयों की संख्या गिनते हैं। यह C(5,4)=5 है (धनात्मक बनाने के लिए 5 में से 4 एक चुनें और पाँचवें को ऋणात्मक रखें: 1+1+1+1-1=3)। DP सही रूप से 5 लौटाता है। यह रूपांतरण चिह्न-आवंटन की समस्या को मानक उपसमुच्चय-गिनती की समस्या में सुंदर ढंग से बदल देता है।
nums में शून्य संभालना
यदि nums में शून्य हों, तो किसी शून्य को + या - देना योग नहीं बदलता। प्रत्येक शून्य मान्य आवंटनों की संख्या दोगुनी कर देता है। DP इसे स्वाभाविक रूप से संभालता है: num=0 को संसाधित करते समय आंतरिक लूप range(new_target, -1, -1) new_target से 0 तक चलता है और dp[c] += dp[c - 0] = dp[c] सभी पहुँच योग्य योगों को दोगुना कर देता है। यदि आप range(new_target, num-1, -1) का उपयोग करते हैं, जो num=0 होने पर new_target से 0 तक शुरू होता है, तो किसी विशेष प्रबंधन की आवश्यकता नहीं होती।
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1जटिलता की तुलना
बलपूर्वक DFS O(2^n) है। मेमोकरणयुक्त DFS की O(n × total) समय और O(n × total) स्थान जटिलता है। रूपांतरण-आधारित 1D DP की O(n × new_target) समय और O(new_target) स्थान जटिलता है, जहाँ new_target ≤ total है। 1D DP मेमोकरण की तुलना में बहुत कम स्थान का उपयोग करता है, क्योंकि रूपांतरण के माध्यम से index आयाम को हटा दिया जाता है।
अन्य नैपसैक समस्याओं से संबंध
लक्ष्य योग नैपसैक की कई अवधारणाओं को जोड़ता है: यह एक आवंटन समस्या के रूप में शुरू होता है, उपसमुच्चय योग में बदलता है (समान उपसमुच्चय योग में विभाजन की तरह), और गिनती के साथ वही 0/1 नैपसैक की पीछे की ओर पुनरावृत्ति वाले प्रारूप का उपयोग करता है (कॉइन चेंज II की तरह)। इन संबंधों में निपुण होने से आप साक्षात्कारों में नई समस्याओं को ज्ञात प्रारूपों से उनकी संरचनात्मक समानता के आधार पर तेज़ी से वर्गीकृत कर सकते हैं।
सीमांत स्थितियाँ और साक्षात्कार संबंधी टिप्पणियाँ
मुख्य मामले: (1) target = total: केवल एक तरीका (सभी धनात्मक); (2) target = -total: केवल एक तरीका (सभी ऋणात्मक); (3) सभी शून्यों के साथ target = 0: उत्तर 2^n है; (4) बहुत बड़ा total लेकिन छोटा n — 1D DP सरणी का आकार total/2 से सीमित होता है। साक्षात्कारों में कोड लिखने से पहले रूपांतरण को मौखिक रूप से चरण-दर-चरण समझाएँ — यही वह स्पष्ट न दिखने वाली अंतर्दृष्टि है जो मजबूत उम्मीदवारों को अलग करती है।
रूपांतरण के बिना 2D DP विकल्प
रूपांतरण के बिना, dp[i][s] को पहली i संख्याओं को चिह्न देने पर योग s तक पहुँचने वाले तरीकों की संख्या के रूप में परिभाषित करें। योग ऋणात्मक हो सकता है, इसलिए total का ऑफ़सेट जोड़ें: dp[i][s + total] का उपयोग करें। इसके लिए (n+1) × (2*total+1) आकार की 2D तालिका चाहिए। यह सही है, लेकिन इसमें अधिक स्थान लगता है और साक्षात्कार के दबाव में रूपांतरण के बाद वाले 1D नैपसैक की तुलना में इसे जल्दी लिखना कठिन है।
त्वरित जाँच
इस पाठ में पढ़ी गई डेटा संरचनाओं और एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी — की अवधारणाओं की अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: लक्ष्य योग चिह्न-आवंटन की समस्या को (target + total) / 2 योग वाले उपसमुच्चयों की गिनती में बदल देता है, 1D 0/1 नैपसैक की पीछे की ओर पुनरावृत्ति O(n × new_target) समय और O(new_target) स्थान में उपसमुच्चयों की गिनती करती है, और शीघ्र वैधता जाँचें (विषम योग, |target| > total) अनावश्यक DP निष्पादन को रोकती हैं। अब हम सबसे छोटे पथ की समस्याओं की ओर बढ़ेंगे, जहाँ डिज्क्स्ट्रा की कलनविधि और प्राथमिकता कतार का उपयोग होता है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग” पाठ निःशुल्क है?
हाँ—“धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग” में मैं क्या सीखूँगा?
लक्ष्य-योग असाइनमेंट समस्या को उपसमुच्चय-योग अंतर वाले नैपसैक में बदलिए और इसे O(n × sum) समय में हल कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- 0/1 नैपसैक और स्थान अनुकूलन
- अनबाउंडेड नैपसैक और Coin Change II
- समान उपसमुच्चय योग में विभाजन
- धनात्मक और ऋणात्मक चिह्नों वाला लक्ष्य योग