मान लीजिए हमारे पास nums नामक एक सरणी और एक मान k है। खंड [left, right] (left ≤ right) का XOR उन सभी तत्वों का XOR है जिनके इंडेक्स left और right के बीच हैं (सम्मिलित)।
हमें सरणी में बदलने के लिए न्यूनतम तत्वों की संख्या ज्ञात करनी है ताकि आकार k के सभी खंडों का XOR शून्य के बराबर हो।
उदाहरण के लिए, यदि इनपुट nums = [3,4,5,2,1,7,3,4,7], k = 3 है, तो आउटपुट 3 होगा क्योंकि हम इंडेक्स 2, 3, 4 पर तत्वों को संशोधित करके सरणी को [3,4,7,3,4,7,3,4,7] बना सकते हैं।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
LIMIT := 1024
temp := आकार LIMIT x k की एक सरणी बनाएं और 0 से भरें।
nums में प्रत्येक इंडेक्स i और मान x के लिए, temp[i mod k, x] := temp[i mod k, x] + 1 करें।
dp := आकार LIMIT की एक सरणी जिसे -2000 से भरें।
dp[0] := 0
temp की प्रत्येक पंक्ति के लिए:
maxprev := dp का अधिकतम।
new_dp := आकार LIMIT की एक सरणी जिसे maxprev से भरें।
पंक्ति में प्रत्येक इंडेक्स i और मान cnt के लिए:
यदि cnt > 0, तो dp के प्रत्येक इंडेक्स j और मान prev के लिए:
new_dp[i XOR j] := new_dp[i XOR j] और (prev + cnt) का अधिकतम।
dp := new_dp
nums का आकार - 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