মনে করুন 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-এ প্রতিটি row-এর জন্য, করুন
maxprev := dp-এর সর্বোচ্চ
new_dp := LIMIT আকারের একটি অ্যারে maxprev দিয়ে পূরণ
row-এ প্রতিটি ইন্ডেক্স 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
