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

Problem Statement:

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

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store