Home/ Questions/Q 228
Answered
Anonymous
  • 0
Asked: 2022-12-26T17:47:49+00:00 In:

How to Solve this coding problem in linear time complexity

  • 0

Given an array containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. How to solve this problem in python in linear time complexity O(n)?

Test Case:

An array between 0 and 4

nums = [0,2,4,1]

output= 3.

coding problemlinear time complexitypython

You must login to add an answer.

Need An Account,

1 Answer

  1. Best Answer
    Begginer
    This answer was edited.

    To solve this problem in linear time complexity (O(n)), you can use the following algorithm:

    1. Initialize a variable range_sum to the sum of the range [0, n], which is calculated using the formula (n * (n+1)) // 2.
    2. Initialize a variable array_sum to the sum of all the elements in the array nums.
    3. Subtract array_sum from range_sum and return the result as the missing number.

    Because the sum of natural numbers is ( n * (n+1) )/2

    Sum of first 4 elements = 1+2+3+4 = 10

    Sum of given 4 elements = 0 + 2 + 4 +1=7

    So, the final difference = 10 – 7 = 3

    Here is some example code in Python that implements this algorithm:

    def findMissingNumber(nums):
    n = len(nums)
    range_sum = (n * (n+1)) // 2
    array_sum = sum(nums)
    return range_sum - array_sum
    print(findMissingNumber([0,2,4,1]))

    Another way to solve this problem:

    1. Initialize a variable sum to the sum of the range [0, n].
    2. Iterate through the array, and for each element x in the array, subtract x from sum.
    3. Return sum the missing number.

    Here is some example code in Python that implements this algorithm:

    def findMissingNumber(nums):
    n = len(nums)
    sum = 0
    for i in range(n + 1):
    sum += i
    for x in nums:
    sum -= x
    return sum
    print(findMissingNumber([0,2,4,1]))

    These are the 2 best possible algorithms that give time complexity of O(n), as it requires iterating through the array once and performing a constant number of operations for each element.

    I hope this helps! Let me know if you have any questions.

    • 1