Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
An alternative solution if we consider that the sum of numbers: 1, 2, 3, ..., n ...

Athanasios Petsas

Feb 10, 2022

An alternative solution if we consider that the sum of numbers: 1, 2, 3, ..., n is 1 + 2 + 3 + ... + n = n * (n+1) / 2, would be to sum all numbers in the loop and return n*(n+1)/2 - sum. Of course it has the same time complexity O(N) and and space complexity O(1) but it's only one pass. I know that the specific lesson follows this approach to demonstrate the pattern and to group similar problems under the same umbrella. I just thought of that solution when saw the problem, that's why I'm posting it here. Quick python code: {code} def find_missing_number(nums): n = len(nums) s = 0 for num in nums: s += num return (n * (n+1) // 2) - s {code}

3

0

Comments
Comments
Design Gurus
Design Gurus4 years ago

Thanks for posting this.

This is a well known solution. Here we are focusing on cyclic sort pattern.

This algorithm can have an integer overflow problem because it requires to sum all numbers of the array. This won't be a problem for pure Python though but languages l...

P
PENG SHI4 years ago

for i in range(len(numbers)): k += i + 1 - numbers(i) return k

On this page