Given a set of elements, how can I find difference between MAX and MIN in all subsets of this list.
给定一组元素,如何在此列表的所有子集中找到MAX和MIN之间的差异。
Eg:
set = 1 2 3
set = 1 2 3
Subset = {1}, max(s)-min(s) = 0.
Subset = {2}, max(s)-min(s) = 0.
Subset = {3}, max(s)-min(s) = 0.
Subset = {1,2}, max(s)-min(s) = 1.
Subset = {2,3}, max(s)-min(s) = 1.
Subset = {1,3}, max(s)-min(s) = 2.
Subset = {1,2,3}, max(s)-min(s) = 2.
So the output will be 1+1+2+2 = 6
2 个解决方案
#1
Sort the list.
对列表进行排序。
After sorting, the i'th element will be minimum in all (and only) subsets that do not include the i-1 first elements, and does include this element. There are 2^(n-i) of those (when i is 1 based).
在排序之后,第i个元素在所有(且仅)的子集中将是最小的,其不包括i-1个第一元素,并且包括该元素。有2 ^(n-i)个(当我基于1时)。
Similarly, i will be the highest element in each subset that does not include any number after i, and do include i, and there are 2^(i-1) such subsets (again, 1 based).
类似地,我将是每个子集中的最高元素,其在i之后不包括任何数字,并且包括i,并且存在2 ^(i-1)个这样的子集(再次,基于1)。
So, after sorting, just iterate, and for each i add:
因此,排序后,只需迭代,并为每个我添加:
arr[i] * (2^(i-1) - 2^(n-i))
Effectively adding the sum by arr[i] * #times_i_is_max, and reducing it by arr[i] * #times_i_is_min
通过arr [i] * #times_i_is_max有效地添加总和,并通过arr [i] * #times_i_is_min减少它
In your example:
在你的例子中:
sorted=1,2,3
1* (2^0 - 2^2) + 2*(2^1 - 2^1) + 3*(2^2 - 2^0) =
1*(-3) + 2*0 + 3*(3) = -3 + 0 + 9 = 6
The bottleneck of this algorithm is the sorting, which is O(nlogn) - after that, everything is done in linear scan of the array.
这个算法的瓶颈是排序,即O(nlogn) - 之后,一切都在数组的线性扫描中完成。
#2
@mukul you can calculate all powers of 2 and store them in an array taking mod simultaneously like
@mukul你可以计算2的所有幂并将它们存储在一个同时采用mod的数组中
a[0]=1; for(i=1;i<any_no;i++)a[i]=(a[i-1]*2)%MOD;
#1
Sort the list.
对列表进行排序。
After sorting, the i'th element will be minimum in all (and only) subsets that do not include the i-1 first elements, and does include this element. There are 2^(n-i) of those (when i is 1 based).
在排序之后,第i个元素在所有(且仅)的子集中将是最小的,其不包括i-1个第一元素,并且包括该元素。有2 ^(n-i)个(当我基于1时)。
Similarly, i will be the highest element in each subset that does not include any number after i, and do include i, and there are 2^(i-1) such subsets (again, 1 based).
类似地,我将是每个子集中的最高元素,其在i之后不包括任何数字,并且包括i,并且存在2 ^(i-1)个这样的子集(再次,基于1)。
So, after sorting, just iterate, and for each i add:
因此,排序后,只需迭代,并为每个我添加:
arr[i] * (2^(i-1) - 2^(n-i))
Effectively adding the sum by arr[i] * #times_i_is_max, and reducing it by arr[i] * #times_i_is_min
通过arr [i] * #times_i_is_max有效地添加总和,并通过arr [i] * #times_i_is_min减少它
In your example:
在你的例子中:
sorted=1,2,3
1* (2^0 - 2^2) + 2*(2^1 - 2^1) + 3*(2^2 - 2^0) =
1*(-3) + 2*0 + 3*(3) = -3 + 0 + 9 = 6
The bottleneck of this algorithm is the sorting, which is O(nlogn) - after that, everything is done in linear scan of the array.
这个算法的瓶颈是排序,即O(nlogn) - 之后,一切都在数组的线性扫描中完成。
#2
@mukul you can calculate all powers of 2 and store them in an array taking mod simultaneously like
@mukul你可以计算2的所有幂并将它们存储在一个同时采用mod的数组中
a[0]=1; for(i=1;i<any_no;i++)a[i]=(a[i-1]*2)%MOD;