Problem:
Find the longest sequence consisting only of 0's, and the longest sequence consisting only of 1's?
Solution:
import sys
longestSequenceForOne = None
startIndexForOne = None
longestSequenceForZero = None
startIndexForZero = None
def setLongestSequence(array, longestSequence, startIndex):
global longestSequenceForOne
global startIndexForOne
global longestSequenceForZero
global startIndexForZero
if array[startIndex] == 1:
if longestSequenceForOne == None or longestSequenceForOne < longestSequence:
longestSequenceForOne = longestSequence
startIndexForOne = startIndex
elif array[startIndex] == 0:
if longestSequenceForZero == None or longestSequenceForZero < longestSequence:
longestSequenceForZero = longestSequence
startIndexForZero = startIndex
def findLongestSequence(array, size):
"""
Find the longest sequence of 0's and 1's
"""
longestSequence = 1
beginIndex = None
index = 1
startIndex = 0
sameElementCount = 1
while (index < size):
if array[index] == array[index-1]:
sameElementCount += 1
elif sameElementCount > longestSequence:
longestSequence = sameElementCount
startIndex = index - sameElementCount
sameElementCount = 1
setLongestSequence(array, longestSequence, startIndex)
else:
sameElementCount = 1
index += 1
if sameElementCount > longestSequence:
longestSequence = sameElementCount
startIndex = index - sameElementCount
setLongestSequence(array, longestSequence, startIndex)
if __name__ == '__main__':
size = int(input())
if size < 2 or size > 100:
sys.exit()
array = [int(x) for x in input().split() if x == '1' or '0']
if len(array) != size:
sys.exit()
findLongestSequence(array, size)
print(startIndexForZero, longestSequenceForZero)
print(startIndexForOne, longestSequenceForOne)
Correctness
Input
12
0 1 0 1 1 1 0 1 0 0 0 0
Output
8 4
3 3
Input
17
1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0
Output
9 4
0 2
Questions:
Does the code require better error handling?
Can this code get more pythonic?
for index in range(size)
is both more pythonic and faster thanwhile (index<size)
. Also, if your array is large, you can significantly improve the run time by incrementing by the current longest sequence instead of by 1. Check out this question of mine - it's not exactly the same, but the general idea of the algorithm still applies. \$\endgroup\$for index in range(1, len(array))
works \$\endgroup\$