procoderpro's blog

By procoderpro, history, 4 months ago, In English,

I recently came across with this question
Here distinct subarray means :- 7 8 9 0 7 8 9 0
Subarray index 0 to 3 and 4 to 8 are same
Constraints are Number of elements NumElements<=1000
a[i]<=200

My solution :- Build the trie of all subarrays and count if distinct leaf has at most k odd numbers in its path

however the memory requirements of Trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in Trie.

which in this case is O(200*NumElements*NumElements*Numelements)

So i am stuck with that ?

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it