# Intuition\nSkip this section if you already know v[i] needs to be equal to v[k * c + i]).\n\nLet\'s take an example array [3,4,7,1] and k = 3.\nThere are two segments in this example. We oberserve that 3^4^7 = 0. So the first segment is fine. And for the second segment, the equation 4 ^ 7 ^ x = 0 has only one solution which is x = 3. So the fourth number has to be 3 if we want to keep the first three numbers. Final array = [3,4,7,3]. Similarly, if there were to be a fifth element, and we want to keep the first four unchanged, then it would have to be 4 because 7 ^ 3 ^ x = 0 gives x = 4. Final array [3,4,7,3,4]. The first k numbers (such that their xor is 0) would have to keep repeating throughout the array.\n\n# How to Approach\nIn general, the target is to make v[i] = v[k * c + i] for all i, where c is an integer.\nArray positions such as k * c + i will be called just i hereafter. So there will be a bunch of i = 0 positions, a bunch of i = 1 positions, and so on up to i = k - 1.\n\nNow, we will only focus on choosing k numbers because we know they need to keep repeating.\n\nWe will first calculate the frequencies of different numbers at all the indices 0 to k - 1.\n\nThen intuition says that the number that has the highest frequency for some index can probably be assigned to this index. A greedy solution can be formed this way. But a problem with this algorithm is breaking ties. Let\'s say at index 5, there are two numbers with the max frequency of 3. Then which one should we select? This selection can really impact the result going forward as this number will be xor\'ed to other numbers that we are yet to see. So we\'ll have to explore both these cases as in DFS. But this may lead to exponential complexity.\n\nThis is when we can think that dp can help.\n\n# Algorithm\n\ndp[i][j] = minimum total number of elements we need to change from index 0 to i so that the xor of the subarray from index 0 to i is equal to j.\n\nCalculating dp[i][j]:\nIndex = i. target xor value = j.\n\nMain task at hand -\nAt index i, we need to select a number x such that x ^ (*some_xor_up_to_index_i-1*)= j.\nWhat are the values we can choose x from? We can choose anything from 0 to 1023.\nThat *some_xor_up_to_index_i-1* = j ^ x.\ndp[i][j] will be the sum of two components:\n**Component 1:** How many changes need to be done up to index i - 1? It is dp[i - 1][j ^ x].\n**Component 2:** How many changes we need to do at index i. It is (total number of times index i occurs) - (frequency of x at index i).\n\nSo far, we know dp[i][j], if we choose x at index i, is sum of component 1 and component 2.\nAnd overall, dp[i][j] = min (dp[i][j] made by choosing x) over all x in [0, 1023]).\n\nIf we iterate over [0, 1023] for the value of x and calculate corresponding answers and then take their minimum to find dp[i][j], that will make the solution\'s overall complexity cubic and we can\'t afford that given the constraints.\n\nBreaking down our search space of x:\n1. Select x whose freq at index i is 0\nIn this case component 2 is same for all such numbers. So the minimum value only depends on component 1 which will be the minimum value of in dp[i - 1]. So there\'s no point iterating over these x\'s. We can do it in one go.\n\n2. Select x such that its freq at index i is greater than 0\nWe need to iterate over such numbers to calculate dp[i][j] for all these x individually because we can\'t know what is best.\n\nFinally dp[k - 1][0] will be the answer because the xor of all the k numbers needs to be 0 as the requirement by the question.\n\n# Time Complexity\nRefer code.\nThe first for loop runs k times.\nThe second for loop runs 1024 times.\nThe third for loop runs n/k times. Explanation: If an array of size n has been split into subarrays of size k, then how many such subarrays will there be? Answer: n/k. So any index of a subarray (a position from 0 to k - 1) can have at max n/k unique value in the different subarrays.\n\nSo overall time complexity = k * 1024 * (n / k) = n * 1024\n\n# Code\n```\nclass Solution {\npublic:\n \n int minChanges(vector& v, int k) {\n int n = v.size();\n \n // freq[i][x] = frequency of the number x at position i where i in [0, k - 1]\n vector > freq(k, vector(1024, 0));\n /* dp[i][j] = minimum total number of elements we need to change from index 0 to i so that\n the xor of the subarray from index 0 to i is equal to j */\n vector > dp(k, vector(1024, n + 1));\n // numsAtPosition[i] = set of unique numbers at position i where i in [0, k - 1]\n unordered_set numsAtPosition[k];\n \n for(int i = 0; i < n; i++) {\n int position = i % k;\n freq[position][v[i]]++;\n numsAtPosition[position].insert(v[i]);\n }\n \n int bestUptoLast = 0;\n \n for(int i = 0; i < k; i++) { // this loop runs k times\n \n // how many i indices exist in the array\n int cntOfPos = n / k + (((n % k) > i) ? 1 : 0);\n \n // will track best value at i\n int bestAti = n + 1;\n \n // find the best way to make the xor sum equal to j from index 0 to i\n for(int j = 0; j < 1024; j++) { // this loop runs 1024 times\n if(i == 0) {\n dp[i][j] = cntOfPos - freq[i][j];\n }\n else {\n \n // iterate over all numbers that occur at index i\n for(auto x : numsAtPosition[i]) { // this loop runs n/k times\n dp[i][j] = min(dp[i][j], dp[i - 1][j ^ x] + cntOfPos - freq[i][x]);\n }\n \n // this will do for all the numbers that don\'t occur at index i\n // we are changing all the numbers at index i with an arbitrary number that gives best result\n dp[i][j] = min(dp[i][j], bestUptoLast + cntOfPos);\n }\n bestAti = min(bestAti, dp[i][j]);\n }\n bestUptoLast = bestAti;\n }\n \n return dp[k - 1][0];\n }\n};\n```\n\nCode inspired by @k_m_066

Make the XOR of All Segments Equal to Zero

Problem Description

Problem Description

Answer Panel