find the missing number in a block of 3 numbers Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.

eg: 11122333 : Missing number 2
11122233344455666 Missing number 5


I think we can't do better than just going from beginning to the end and checking the count if a specific number count is less than 3.

s = "11122233344455666"
count = 1
flag = 0
for i in range(0, len(s), 3):
    if i+2 &lt; len(s) and s[i] != s[i + 2]:
        print s[i]
        break
    elif i+2 &gt;= len(s):
        print s[i]
        break
Your current algorithm is linear in the size of your array $A$, which I'll call $n$. We can do a bit better, by observing the following: If some index $3i-1$ comes before the missing number, then $A[3i-1]=i$. Otherwise, $A[3i-1]=i+1$. (I start indexing at $0$) 

So, we can do a binary search on $i$, as we always can see whether the index of the missing number is larger or smaller than $3i-1$. This gives an $O(\log n)$ algorithm, which is an improvement on your linear time algorithm.