# Counting a number of sequences where the item is the most frequent one Consider an array $$a$$, where elements are numbers. Consider all subsequence of $$a$$. For each subsequence $$s$$, we find an element $$k$$ with the largest number of occurrences in $$s$$ (if there are several options, choose the smallest such $$k$$).

Problem: for each number $$k$$, find the number of subsequences of $$a$$ for which $$k$$ is the chosen number.

Example:

``Input: [1, 2, 2, 3] Output: 1 -> 6 (, [1, 2], [1, 2'], [1, 3], [1, 2, 3], [1, 2', 3]) 2 -> 8 (, [2'], [2, 3], [2', 3], [2, 2'], [1, 2, 2'], [2, 2', 3], [1, 2, 2', 3]) 3 -> 1 () ``

My idea is that, I make a map $$cnt$$ where $$cnt[x]$$ is number of times $$x$$ occurred in array $$x$$. I am trying to find the answer for $$k$$ then i will create a map $$temp$$ where $$temp[i]=\min(cnt[k], cnt[i])$$. Then consider the value of $$cnt[k]$$ to be $$m$$ then in a subset element $$k$$ can occur from $$0$$ to $$m$$ times and using this i will find answer for all of its occurrences from $$0$$ to $$m$$ which is a simple number of sub sets problem and finally i will have my answer.

But the complexity of my algorithms is bad as it is quadratic or worse. Can it be improved? Posted on Categories proxies