मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और एक धनात्मक मान K है। हम nums पर इन तीन ऑपरेशनों में से कोई भी कर सकते हैं:
- एक संख्या को ऋणात्मक बनाएं
- संख्या में उसका इंडेक्स (1 से शुरू) जोड़ें
- संख्या से उसका इंडेक्स घटाएं
अंत में, हमें जांचना है कि क्या प्रत्येक तत्व पर ये ऑपरेशन केवल एक बार करके सरणी को इस तरह बदला जा सकता है कि सरणी का योग k हो जाए।
उदाहरण के लिए, यदि nums = [1, 2, 3, 7], k = 8 है, तो आउटपुट True होगा क्योंकि हम 2 और 3 से उनके इंडेक्स घटाकर सरणी को [1, 0, 0, 7] बना सकते हैं, अब योग 8 = k है।
हल करने का तरीका
- डायनामिक प्रोग्रामिंग का उपयोग करें
- is_ok() फ़ंक्शन परिभाषित करें जो मेमोइजेशन के साथ पुनरावर्ती रूप से जांचता है
- प्रत्येक तत्व के लिए तीन विकल्प आजमाएं: मूल मान, मान - 2×nums[i], मान ± (i+1)
- यदि अंत में कुल == k, तो True लौटाएं
उदाहरण
size = 100
def is_ok(i, total, k, nums, table):
n = len(nums)
if total <= 0:
return False
if i >= n:
if total == k:
return True
return False
if table[i][total] != -1:
return table[i][total]
table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total]
table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
return table[i][total]
def solve(nums, k):
total = sum(nums)
table = [[-1] * size for _ in range(size)]
return is_ok(0, total, k, nums, table)
nums = [1, 2, 3, 7]
k = 8
print(solve(nums, k))
इनपुट
[1, 2, 3, 7], 8
आउटपुट
True
