Count subsets of array which qualify min(subset) max(subset)

Was asked this question in an interview, didn't have a better answer than generating all possible subsets. Example:

a = [4,2,5,7] k = 8

output = 4

[2],[4,2],[2,5],[4,2,5]

Interviewer tried implying sorting the array should help, but I still couldn't figure out a better-than-brute-force solution. Will appreciate your input.

CodePudding user response：

The interviewer implied that sorting the array would help and it does help. I'll try to explain.

Taking the array and k values you stated:

a = [4,2,5,7]
k = 8

Sorting the array will yield:

a_sort = [2,4,5,7]

Now we can consider the following procedure:

set ii = 0, jj = 1
choose a_sort[ii] as a part of your subset

2.1. If 2 * a_sort[ii] >= k, you are done. else, the subset [a_sort[ii]] holds the condition and is a part of the solution.
add a_sort[ii jj] to your subset

3.1. If a_sort[ii] a_sort[ii jj] < k,

3.1.1. the subset [a_sort[ii], a_sort[ii jj]] holds the condition and is a part of the solution, as well as any subset which consists of any additional number of elements a_sort[kk] where ii< kk < ii jj

3.1.2. set jj = 1 and go back to step 3.

3.2. else, set ii = 1, jj = ii 1, go back to step 2

With your input this procedure should return:

[[2], [2,4],[2,5],[2,4,5]]
# [2,7] results in 9 > 8 and therefore you move to [4]
# Note that for [4] subset you get 8 = 8 which is not smaller than 8, we are done

Explenation

if you have a subset of [a_sort[ii]] which does not hold 2 * a_sort[ii] < k, adding additional numbers to the subset will only yield min(subset) max(subset) > 2 * a_sort[ii] > k and therefore there will not be any additional subsets which hold the wanted condition. Moreover, by setting a subset of [a_sort[ii 1]] will results in 2 * a_sort[ii 1] >= 2 * a_sort[ii] > k` sinse a_sort is sorted. Therefore you will not find any additional subsets.
for jj > ii, if a_sort[ii] a_sort[ii jj] < k then you can push any number if members from a_sort into the subset, as long as the index kk will be bigger than ii and lower than ii jj since a_sort is sorted, and adding these members to the subset will not change the value of min(subset) max(subset) which will remain a_sort[ii] a_sort[ii jj] and we already know that this value is smaller thank k

Getting the count

In case you simply want to the possible subsets, this can be done easier than generating the subsets themselves.

Assuming that for ii > jj the condition holds, i.e. a_sort[ii] a_sort[ii jj] < k. If jj = ii 1 there is an addition of 1 possible subset. If jj > ii 1 there are jj - ii - 1 additional elements which can be either present not not without a change of the value a_sort[ii] a_sort[ii jj]. Therefore there are a total of 2**(jj-ii-1) additional subsets available to add to the solution group (jj-ii-1 elements, each is independently present or not). This also holds for jj = ii 1 since in this case 2**(jj-ii-1) = 2**0 = 1

Looking at the example above:

[2] adds 1 count
[2,4] adds 1 count (1 = 0 1)
[2,5] adds 2 counts (2 = 0 2 --> 2 **(2 - 0 - 1) = 2**1 = 2)

A total count of 4

CodePudding user response：

Sort the array
For an element x at index l, do a binary search on the array to get index of the maximum integer in the array which is < k-x. Let the index be r.
For all subsets where min(subset) = x, we can have any element with index in range (l,r]. Number of subsets with min(subset) = x becomes the total number of possible subsets for (r-l) elements, so count = 2^(r-l) (or 0 if r<l).
(Note: in all such subsets, we are fixing x. That's why the range (l,r] isn't inclusive of l)
You have to iterate over the array, use the above process for each element/index to get the count of subsets where our current element is the minimum and the subset satisfies the given constraint. If you find an element with count=0, break the iteration.

This should work with a 0(N*log(N)) complexity, good enough for an interview question imo.

For the given example, sorted array = [2,4,5,7].

For element 2, l=0 and r=2. Count = 2^(2-0) = 4 (covers [2],[4,2],[2,5],[4,2,5]
For element 4, l=1 and r=0. Count = 0, and we break the iteration.