We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Missing Number In Arithmetic Progression

Number: 1164

Difficulty: Easy

Paid? Yes

Companies: Audible

Problem Description

Given an array representing an arithmetic progression where one element (other than the first or last) has been removed, find the missing value that would restore the progression.

Key Insights

  • The complete arithmetic progression has equal differences between consecutive numbers.
  • The missing element can be found by calculating the expected common difference using the first and last elements.
  • Since exactly one number is missing, iterate through the provided array to detect where the difference deviates from the expected common difference.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

We first compute the expected common difference (diff) for the original arithmetic progression. Since the actual progression had one more element than the current array, the formula used is: diff = (last element - first element) / (n) where n is the length of the current array. Next, iterate over the array and check the difference between each pair of consecutive elements. When the actual difference deviates from diff, it indicates that the missing number is the previous element plus diff. This approach uses a simple loop and constant extra space.

Code Solutions

# Function to find the missing number in the arithmetic progression
def missingNumber(arr):
    # Calculate the expected difference using the first and last elements
    n = len(arr)
    diff = (arr[-1] - arr[0]) // n  # integer division because values are integers
    # Iterate over the array to find the place where the difference deviates from diff
    for i in range(len(arr) - 1):
        # If the difference between consecutive numbers is not equal to the expected diff
        if arr[i+1] - arr[i] != diff:
            # Return the missing number which should be current number + diff
            return arr[i] + diff
    # Return -1 if no missing number is found (should not happen given the problem constraints)
    return -1

# Example usage:
# print(missingNumber([5,7,11,13]))  # Output should be 9
← Back to All Questions