Given a sequence of heads and tails I want to count the number significant substrings in which the number of heads is not less than the number of tails. I want to achieve this in O(NlogN) time.
Example input: [ 'H', 'T', 'H', 'T', 'T', 'H' ]
Example output:
11
Explanation:
{H} {H} {H}
{H, T} {T, H} {H, T} {T, H}
{H, T, H}
{H, T, H, T}
{H, T, T, H}
{H, T, H, T, T, H}
I believe my current algorithm is O(N^2). I solve the problem recursively, iterating with the list of coins sliced on either end.
Here is my current algorithm. How can I achieve O(NLogN) time?
def count_sequences( data ):
print go(range(0,len(data)),data)
seen = set()
def go(rang,data):
if tuple(rang) in seen: return 0
seen.add(tuple(rang))
h = 0
summ = 0
if len(rang)==0: return 0
for i in rang:
if data[i] == 'H': h += 1
summ += go(rang[1:],data)
summ += go(rang[:-1],data)
if len(rang) == 1:
if h ==1: return 1
else: return 0
if h > (len(rang)-1)/2 :
return 1 + summ
else: return summ
Here's an O(n) solution.
Imagine instead of H and T, you had 1 and -1 in your array. This reduces the problem to computing the number of non-negative sum subarrays. This is a known problem that can be solved computing the accumulated array and finding the number of inversions.
This can be naively computed in O(n^2) searching for pairs i < j where A[i]>A[j]. It can be optimized to O(n log n) using a merge sort variant.
But in this case specially, the values in the array can be at most n, and consecutive values have absolute difference of exactly 1, so we can create an algorithm that computes those inversions on the fly in O(n):
def solve(A):
count = 0
accum = 0
total = 0
seen = {0: 1}
for i, element in enumerate(A):
if element == 'H':
count += 1
accum -= seen.get(count, 0)
else:
accum += seen.get(count, 0)
count -= 1
seen[count] = seen.get(count, 0) + 1
total += (i + 1 - accum)
return total
print solve([ 'H', 'T', 'H', 'T', 'T', 'H' ])
print solve([ 'T', 'H', 'H', 'H', 'T' ])
This algorithm is largely based on the one I've read here.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments