Advertisement
Guest User

Untitled

a guest
Jul 25th, 2017
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.86 KB | None | 0 0
  1. A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
  2.  
  3. Your goal is to find that missing element.
  4.  
  5. Write a function:
  6. ```
  7. def solution(A)
  8. ```
  9. that, given a zero-indexed array A, returns the value of the missing element.
  10.  
  11. For example, given array A such that:
  12.  
  13. A[0] = 2
  14. A[1] = 3
  15. A[2] = 1
  16. A[3] = 5
  17. the function should return 4, as it is the missing element.
  18.  
  19. Assume that:
  20.  
  21. + N is an integer within the range [0..100,000];
  22. + the elements of A are all distinct;
  23. + each element of array A is an integer within the range [1..(N + 1)].
  24. Complexity:
  25.  
  26. + expected worst-case time complexity is O(N);
  27. + expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
  28. + Elements of input arrays can be modified.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement