所有子阵列的xor之和

问题描述 投票:0回答:1

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位设置的子数组的数量。

algorithm xor bitset
1个回答
0
投票

这是一个很好的例子,说明程序的更细致,描述性的表述可以使它更容易理解,也更正确。

我们分别看每一位。

让我们考虑第一个循环:它计算从索引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,因为我们传递了一个设置位的实例,我们可以翻转之前有的所有子数组甚至算上我们的新措施。

© www.soinside.com 2019 - 2024. All rights reserved.