在the approach described below的实现中,我没有得到这两个循环如何考虑测试用例的哪一部分,我的意思是这两个循环如何涵盖所有可能性。请帮忙
问题链接xor subbarray
// loop to calculate initial
// value of c_odd
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
odd = (!odd);
if (odd)
c_odd++;
}
还有这个
for (int j = 0; j < n; j++) {
sum += (mul * c_odd);
if ((arr[j] & (1 << i)) > 0)
c_odd = (n - j - c_odd);
}
Geeks for Geeks的描述:
最佳解决方案:为了更好地理解,我们假设元素的任何位由变量'i'表示,变量'sum'用于存储最终总和。
这里的想法是,我们将尝试找到第i位设置的XOR值的数量。让我们假设,有'Si'个子数组,第i位设置。对于第i位,sum可以更新为sum + =(2i * S)。
那么,问题是如何实现上述想法?
我们将把任务分解为多个步骤。在每一步,我们将尝试找到第i位设置的XOR值的数量。现在,我们将每个步骤分解为子步骤。在每个子步骤中,我们将尝试查找从索引'j'(其中j在0到n-1之间变化)的子数组的数量,其中第i位设置在XOR值中。因为,要设置第i位,子数组的奇数个元素应该具有第i位设置。对于所有位,在变量c_odd中,我们将存储从j = 0开始的子数组的计数,其中第i位设置在奇数个元素中。然后,我们将迭代遍历数组的所有元素,在需要时更新c_odd的值。如果我们使用第i位设置到达元素'j',我们将c_odd更新为c_odd =(n - j - c_odd)。这是因为,由于我们遇到了一个设置位,所以具有偶数个元素且具有第i位设置的子数组的子数将切换到具有奇数个元素且具有第i位设置的子数组的数量。
这是一个很好的例子,说明程序的更细致,描述性的表述可以使它更容易理解,也更正确。
我们分别看每一位。
让我们考虑第一个循环:它计算从索引0开始的子阵列有多少当前位集的奇数计数。 (看来如何实现这一计数似乎很清楚,但随时可以问。)
现在,在第二个循环中,我们可以使用这些信息(并更新它)作为我们当前启动的所有子数组(而不是从索引0开始)并在以后的任何地方结束。假设初始计数为2,并且n = 10
,并且当前位设置在数组中索引4和6处的元素上。
现在,在每次迭代中,我们都在标记我们正在计算的子数组的左/下界。我们已经知道有2个子数组从索引0开始并在“稍后某个地方”结束。但是因为在索引4之前没有这个位设置的实例,我们可以说这个计数对于下限1,2,3和4也是正确的:从那些索引开始并且稍后“某处结束”的子数组有2个计数。 “
当我们达到指数4时,魔术就会发生,我们需要更新我们的计数。如果直到现在,有2个子阵列,奇数计数位i
设置从这里开始并结束“稍后”,有10 - here - 2
子阵列,偶数计数位i
设置从这里开始并结束“以后”(A [4..4 ],A [4..5],... A [4..9]但不包括A [4..4]和A [4..5],只有一个位i
设置计数)。
当我们到达索引4时,我们重新计算子数组的计数,其中奇数计数位i
设置从这里开始并以“稍后某个地方”结束为n - j - current_odd_count
,因为我们传递了一个设置位的实例,我们可以翻转之前有的所有子数组甚至算上我们的新措施。