If we are given an array and we have to find out the total no of subsequence having frequency of all elements same then how can we calculate in polynomial time complexity?
For eg., A=[1,2,1]
possible subsequences having every element as same frequency are
[1],[2],[1],[1,2],[2,1]
Hence answer should be 6.
How to solve the subsequence having elements of same frequency in polynomial time complexity?
for an array [5,10,2],answer should be 7 because possible subsequences are [5],[10],[2],[5,10],[5,2],[10,2],[5,10,2]
Hey @rohangupta569 ,
Okay for this problem what we can do is store all the numbers in a frequency map --> O(N)
Every individual element will always satify the condition
Now , find the maximum freq in the map --> O(N)
run the loop from 1 to maxFreq and count for every freq how many elements are there -> O(N^2)
lets say for some freq k elements are there , the number of subsequences of k elements will be 2^k --> O(1)
Therefore , the question is solved in polynomial time complexity .
Try it once . Hope it helps !!
Happy coding !!