Algorithm: Find smallest subset containing K 0's
- by Vishal
I have array of 1's and 0's only. Now I want to find contiguous subset/subarray which contains at least K 0's.
Example
Array is 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 0 0
and K(6) should be 0 0 1 0 1 1 0 0 0 or 0 0 0 0 1 0 1 1 0....
My Solution
Array: 1 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0
Index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Sum: 1 2 2 3 4 4 5 6 6 6 6 6 7 7 8 9 9 9 9 10 11 11 11
Diff(I-S): 0 0 1 1 1 2 2 2 3 4 5 6 6 7 7 7 8 9 10 10 10 11 12
For K(6)
Start with 9-15 = Store difference in diff.
Next increase difference
8-15(Difference in index)
8-14(Compare Difference in index)
So on keep moving to find element with least elements...
I am looking for better algorithm for this solution.