Missing Number In Arithmetic Progression

1
2
3
4
5
6
7
8

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        difference = (arr[-1] - arr[0]) // n
        for i in range(1, n):
            if arr[i] - arr[i - 1] != difference:
                return arr[i] - difference  # If the difference doesn't match, the missing number is found
        return arr[0] - difference if arr[1] - arr[0] != difference else arr[-1] + difference

The Python function missingNumber is designed to find the missing number in an arithmetic progression represented by the list arr.

Here’s how the function works:

  1. It starts by determining the length n of the list arr and calculating the common difference difference of the arithmetic progression. This difference is calculated as (arr[-1] - arr[0]) // n, which is the difference between the first and the last elements divided by the number of terms.

  2. It then iterates over the list from the second element to the end. For each index i, it checks whether the difference between arr[i] and arr[i - 1] equals the common difference difference. If the difference does not match, the function returns arr[i] - difference, which is the missing number.

  3. If no missing number is found in the loop (which means that the missing number is either the first or the last number), the function checks whether the difference between the first two elements is equal to the common difference difference. If not, it returns arr[0] - difference, which is the missing number. Otherwise, it returns arr[-1] + difference, which is the missing number.

This function effectively uses the properties of arithmetic progression to find the missing number in a single pass, resulting in a time complexity of O(n), where n is the number of elements in the list arr. The space complexity is O(1) as no extra space is used apart from the input list.

Arithmetic Sequence Sum

An arithmetic sequence is a sequence of numbers where the difference between any two consecutive numbers is constant. For example, [2, 4, 6, 8] is an arithmetic sequence where the common difference is 2.

The sum of an arithmetic sequence can be easily calculated using a simple formula: it is equal to the average of the first and last number, multiplied by the total number of elements. This formula is usually written as (first + last) * n / 2.

In this problem, we know that the sequence is an arithmetic sequence and a number was removed from it. We also know that the removed number is not the first or the last number of the sequence.

We calculate the minimum and maximum numbers in the sequence, which are the first and last elements of the original sequence. Then, we calculate what the sum of the full sequence would have been, using the formula mentioned above.

We also calculate the actual sum of the sequence with a missing number. The difference between the calculated sum and the actual sum will be the missing number, because that’s the only number that’s not included in the actual sum.

1
2
3
4
5
6
7
8
9

def missingNumber(self, A: List[int]) -> int:
    first = last = A[0]
    sum = 0
    n = len(A)
    for a in A:
        first = min(first, a)
        last = max(last, a)
        sum += a
    return (first + last) * (n + 1) // 2 - sum

Please note that in Python, integer division is performed using the // operator, not the / operator. The / operator performs floating point division in Python. Since your function is expected to return an integer, we use // for integer division.

The function missingNumber is designed to find the missing number in an arithmetic progression represented by the list A.

Here’s how the function works:

  1. It starts by initializing first and last to the first element of A and sum to 0. first and last will keep track of the smallest and largest numbers in the list, while sum will accumulate the total of all numbers.

  2. It then iterates over the list. For each number a, it updates first and last to be the minimum and maximum of their current values and a, respectively, and adds a to sum.

  3. After the loop, first and last are the smallest and largest numbers in the list, respectively, and sum is the total of all numbers.

  4. The missing number is then calculated as (first + last) * (n + 1) // 2 - sum. The expression (first + last) * (n + 1) // 2 is the formula for the sum of an arithmetic progression with n + 1 terms (since one number is missing), first as the first term, and last as the last term. Subtracting sum gives the missing number.

This function effectively uses the properties of arithmetic progression and the formula for the sum of an arithmetic progression to find the missing number in a single pass, resulting in a time complexity of O(n), where n is the number of elements in the list A. The space complexity is O(1) as no extra space is used apart from the input list.

Q&A

I have a similar question. Give an arithmetic progression but there is an error number that makes the common difference different. Find the error number.

For example [6,12,18,22,24,30], the common difference is 6. The error number is 22 because the common difference for 22 is different from others.

How to solve this problem with a binary search?

The problem can be solved using a binary search by focusing on the difference between elements. The logic here is to try and identify the segment of the array where the difference doesn’t match the common difference. This segment will contain the erroneous number. Let’s denote diff as the common difference.

Here’s a Python solution using binary search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def findErrorNum(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] - nums[0] != mid * diff:
            # If the difference in the left half doesn't match with the common difference,
            # the erroneous number must be in the left half
            right = mid
        else:
            # else it's in the right half
            left = mid + 1
    return nums[left]

nums = [6, 12, 18, 22, 24, 30]
diff = (nums[-1] - nums[0]) // len(nums)  # common difference
print(findErrorNum(nums))  # Output: 22

This function works by repeatedly dividing the array into two halves. If the difference in the left half matches the common difference, the erroneous number must be in the right half, so we update left to mid + 1. If not, the erroneous number is in the left half, so we update right to mid. When left and right converge, they will point to the erroneous number.

Remember, this function assumes the input array is sorted. If not, you’ll need to sort the array before running this function.