-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.

Improve this question
7
  • 1
    Seems self-explanatory to me. Commented Sep 6, 2014 at 2:21
  • 1
    (Google "big o notation") Commented Sep 6, 2014 at 2: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. Commented Sep 6, 2014 at 2:22
  • en.wikipedia.org/wiki/Big_O_notation Commented Sep 6, 2014 at 2:23
  • the set {0, 1, ..., n-1} contains n elements... there's no confusion at all Commented Sep 6, 2014 at 2:24

2 Answers 2

Reset to default
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?

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

That hint is far too easy - and it wasn't even preceded by a spoiler alert. Boo! Hiss!
StarterProg. Why are you asking me? Why don't you just do it?
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}.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.