Count of only repeated elements in a sorted array of consecutive elements using binary search
# Python3 program to find the
# only repeated element and
# number of times it appears
# Assumptions : vector a is sorted,
# max-difference of two adjacent
# elements is 1
def sequence(a):
if (len(a) == 0):
return [0, 0]
s = 0
e = len(a) - 1
while (s < e):
m = (s + e) // 2
# if a[m] = m + a[0], there is no
# repeating character in [s..m]
if (a[m] >= m + a[0]):
s = m + 1
# if a[m] < m + a[0], there is a
# repeating character in [s..m]
else:
e = m
return [a[s], len(a) - (
a[len(a) - 1] - a[0])]
# Driver code
if __name__ == "__main__":
p = sequence([1, 2, 3, 4, 4, 4, 5, 6])
# Function call
print("Repeated element is", p[0],
", it appears", p[1], "times")