0% completed
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
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...
PENG SHI4 years ago
for i in range(len(numbers)): k += i + 1 - numbers(i) return k
On this page