Sum of width of subsequences- Coding question asked by Atlassian, Apple

Problem Statement:

Given an sequence of integers, return the sum of the widths of all the non-empty subsequences of the subsequence. Since the answer may be very large, return it modulo 10⁹ + 7

The width of a sequence is the difference between the maximum and minimum elements in the sequence.

Input format :

An array vector.

Output format :

An integer representing sum of widths of all possible subsequences.

Sample Input:

[2,1,3]

Sample Output:

6

Explanation of Output:

The subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

Approach:

One of the ways to solve the problem is first finding all possible subsequences recursively and adding width during each recursion. The code for above is lengthy and has high time complexity of O(2^n). This will lead to time limit exceeded for very large subsequences.

To solve the question in lower time complexity, first we have to look whether changing the order of elements(indices wise) creates any impact on answer on not. As we only need to find sum of difference of maximum and minimum differences, we can do so by sorting the array.

After that, mathematically the sum of subsequences is equal to

Time complexity: O(n*log(n))

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.