Question
app.codility.com
My Solution
app.codility.com
def solution(A):
length = len(A)
stack = [0]*length
size = 0
for i in range(length):
if size == 0:
stack[size] = A[i]
size += 1
elif stack[size-1] != A[i]:
size -=1
else:
stack[size] = A[i]
size += 1
count = 0
for i in range(length):
if A[i] == stack[size-1]:
count += 1
hasDominator = 0
if count > length/2:
hasDominator = 1
else:
return 0
prefixSum = [0]*length
curSum = 0
for i in range(length):
if A[i] == stack[size-1]:
curSum += 1
prefixSum[i] = curSum
ans = 0
for i in range(length):
if prefixSum[i] > (i+1)/2 and prefixSum[length-1]-prefixSum[i] > (length-i-1)/2:
ans += 1
return ans