-1

Can someone explain what this question is asking for?

Array A contains n‐1 unique integers in the range [0,n‐1] and there is one number from this range that is not in A. Design an O(n) algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself.

Does this question means the length of the array is (for example: 5). And array contains = {0,1,x,3,4}. Find x?

What is O(n) and O(1)? How do I find the missing number in the array using O(n) algorithm?

Help is appreciated. Thanks.

Zainau
  • 95
  • 4
  • 13
  • 1
    Seems self-explanatory to me. – Hot Licks Sep 06 '14 at 02:21
  • 1
    (Google "big o notation") – Hot Licks Sep 06 '14 at 02:21
  • No, it's a bit confusing, but it seems to be saying that there are `n` possible numbers, and only `n-1` of these are in the array, so you have to find the missing one. Think about it: in the range `[0,n-1]`, there are `n` unique integers. – jackarms Sep 06 '14 at 02:22
  • http://en.wikipedia.org/wiki/Big_O_notation – Barranka Sep 06 '14 at 02:23
  • the set `{0, 1, ..., n-1}` contains `n` elements... there's no confusion at all – Barranka Sep 06 '14 at 02:24
  • It's a very simple problem, intentionally obfuscated. Don't let it scare you. – Hot Licks Sep 06 '14 at 02:30
  • Hint: Use the sum of arithmetic series. Also look up Big O notation, specifically constant time and linear time. That should be all you need to solve the problem. It is basic first grade level math, you just gotta design the algorithm for it. – Shashank Sep 06 '14 at 03:17

2 Answers2

1

Does this question means the length of the array is (for example: 5). And array contains = {0,1,x,3,4}. Find x?

Yes. (More or less)

What is O(n) and O(1)?

Read your algorithmics text book. Or your lecture notes. Or http://en.wikipedia.org/wiki/Big_O_notation.

How do I find the missing number in the array using O(n) algorithm?

That would be solving the problem for you!

Hint: what is the formula for the sum of 1 to N?

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
0

Does this question means the length of the array is (for example: 5). And array contains = {0,1,x,3,4}. Find x?

not exactly: if n was 5, the array would contain four unique naturals from 0 to 4 (n-1): {3, 1, 4, 0}.

greybeard
  • 2,249
  • 8
  • 30
  • 66