Problem statement

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

Solution 1

One way to solve this problem is to find diff: step of our progression and then find missing number.

Complexity

Time complexity is O(n), space complexity is O(n) as well.

Code

class Solution:
    def missingNumber(self, arr):
        diff = (arr[-1] - arr[0])//(len(arr))
        if diff == 0: return arr[0]
        real = set(range(arr[0], arr[-1] + diff, diff))
        return list(real - set(arr))[0]

Solution 2

There is better solution, using binary search. The idea is to check if number we see on the place mid is what we expected to see. Depending on this we go to the left or to the right half.

Complexity

Time complexity is O(log n), space complexity is O(1)

Code

class Solution:
    def missingNumber(self, arr):
        diff = (arr[-1] - arr[0])//(len(arr))
        beg, end = 0, len(arr) - 1
        while beg < end:
            mid = (beg + end)//2
            if arr[mid] == arr[0] + mid*diff:
                beg = mid + 1
            else:
                end = mid
                
        return arr[0] + diff * beg