[Solved] Number of distinct subarrays with atmost k odd elements.

Revision en10, by procoderpro, 2018-10-18 19:15:53

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English procoderpro 2018-10-18 19:15:53 0 (published)
en9 English procoderpro 2018-10-18 19:15:15 9 (saved to drafts)
en8 English procoderpro 2018-10-17 20:58:45 0 (published)
en7 English procoderpro 2018-10-17 20:58:31 8 Tiny change: ' leaf has k odd num' -> ' leaf has at most k odd num' (saved to drafts)
en6 English procoderpro 2018-10-17 20:39:34 0 (published)
en5 English procoderpro 2018-10-17 20:38:40 166
en4 English procoderpro 2018-10-17 20:38:07 44
en3 English procoderpro 2018-10-17 20:37:21 99
en2 English procoderpro 2018-10-17 20:35:23 396 Tiny change: 'ents<=1000\na[i]<=20' -> 'ents<=1000 \na[i]<=20'
en1 English procoderpro 2018-10-17 20:28:48 187 Initial revision (saved to drafts)