मान लीजिए कि हमारे पास nums नामक एक सरणी है और दूसरा मान k है। एक खंड का एक्सओआर [बाएं, दाएं] (बाएं <=दाएं) उन सभी तत्वों का एक्सओआर है जिनके सूचकांक बाएं और दाएं (समावेशी) के बीच हैं।
हमें ऐरे में बदलने के लिए तत्वों की न्यूनतम संख्या इस तरह ढूंढनी होगी कि आकार k के सभी खंडों का XOR शून्य के समान हो।
इसलिए, यदि इनपुट संख्या =[3,4,5,2,1,7,3,4,7], के =3 की तरह है, तो आउटपुट 3 होगा क्योंकि हम सूचकांक 2, 3 पर तत्वों को संशोधित कर सकते हैं, 4 सरणी बनाने के लिए [3,4,7,3,4,7,3,4,7]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
सीमा :=1024
-
अस्थायी:=एक सरणी बनाएं जिसका आकार LIMIT x k है, और 0 से भरें
-
प्रत्येक अनुक्रमणिका के लिए i और मान x अंकों में, करें
-
अस्थायी [मैं मॉड के, एक्स]:=अस्थायी [मैं मॉड के, एक्स] + 1
-
-
dp:=आकार की एक सरणी LIMIT और -2000 से भरें
-
डीपी [0] :=0
-
अस्थायी में प्रत्येक पंक्ति के लिए, करें
-
मैक्सप्रेव :=अधिकतम डीपी
-
new_dp :=आकार की एक सरणी LIMIT और maxprev से भरें
-
प्रत्येक अनुक्रमणिका i और मान cnt पंक्ति के लिए, करें
-
अगर cnt> 0, तो
-
प्रत्येक अनुक्रमणिका j और dp में प्रचलित मान के लिए, करें
-
new_dp[i XOR j] :=अधिकतम new_dp[i XOR j] और पिछला+cnt
-
-
-
-
डीपी:=new_dp
-
-
अंकों का वापसी आकार - new_dp[0]
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
def solve(nums, k):
LIMIT = 2**10
temp = [[0 for _ in range(LIMIT)] for _ in range(k)]
for i,x in enumerate(nums):
temp[i%k][x] += 1
dp = [-2000 for _ in range(LIMIT)]
dp[0] = 0
for row in temp:
maxprev = max(dp)
new_dp = [maxprev for _ in range(LIMIT)]
for i,cnt in enumerate(row):
if cnt > 0:
for j,prev in enumerate(dp):
new_dp[i^j] = max(new_dp[i^j], prev+cnt)
dp = new_dp
return len(nums) - new_dp[0]
nums = [3,4,5,2,1,7,3,4,7]
k = 3
print(solve(nums, k)) इनपुट
[3,4,5,2,1,7,3,4,7], 3
आउटपुट
-9