891. Sum of Subsequence Widths[TODO]

It is extremely tricky!


long count = (long)(
                (1l << i) - (1l << (len - 1 - i))
                )% mod;



19.43 %
class Solution {
    public int sumSubseqWidths(int[] A) {
        if (A == null) {
            return 0;
        }
        Arrays.sort(A);
       
        // 0
        //[1, 2, 3]
       
        // index  i  len - 1 - i
        //   0    0    2
        //   1    1    1
        //   2    2    0
        int len = A.length;
        long mod = (long)(1e9 + 7);
        long result = 0;
        long count = 1;
        for (int i = 0; i < len; i++) {
            // A[i] as upper bound -> 2^i
            // A[i] as lower bound -> 2^(len - 1 - i)
            result = (result + count * ((A[i] - A[len - 1 - i]) % mod)) % mod;
            count = (count << 1) % mod;
        }
        return (int)result;
    }
}

[I read the question wrong... It is sub-sequence instead of sub array!]
Everyone says order doesn't matter, but I don't know why it doesn't matter
Sub-array example
Original
[5, 6, 1, 3]      min/max
[5]                   5 5           
[5,6]                5 6
[5,6,1]             1 6
[5,6,1,3]          1 6
   [6]                6 6
   [6,1]             1 6
   [6,1,3]          1 6
      [1]             1 1
      [1,3]          1 3 
         [3]          3 3
After sorting
[1, 3, 5, 6]      min/max
[1]                   1 1           
[1,3]                1 3
[1,3,5]             1 5
[1,3,5,6]          1 6
   [3]                3 3
   [3,5]             3 5
   [3,5,6]          3 6
      [5]             5 5
      [5,6]          5 6 
         [6]          6 6