Solution


Approach 1: Mathematical

Intuition

Let's try to count the number of subsequences with minimum A[i] and maximum A[j].

Algorithm

We can sort the array as it doesn't change the answer. After sorting the array, this allows us to know that the number of subsequences with minimum A[i] and maximum A[j] is . Hence, the desired answer is:

Complexity Analysis

  • Time Complexity: , where is the length of A.

  • Space Complexity: , the space used by pow2. (We can improve this to space by calculating these powers on the fly.)


Analysis written by: @awice.