
December 4th, 2015, 11:43 AM
#1
Given an array that contains numbers from 1 to 1+n
Hello I have to do a task, but not sure how to proceed please could someone help me I would be really thankful so the thing I have to do is the following:
You are given an array A of size n that contains numbers in the range
1 to n + 1. We know that each number occurs at most once in A. Because there are only n
numbers in A out of n + 1 possible numbers, exactly one of the numbers is missing.
(a) Give a worstcase O(n) time algorithm that determines the missing number. Also prove
the running time of your algorithm.
(b) If the array A was sorted, we could find the missing number in O(log n) time instead.
Give an algorithm that finds the missing number in a sorted array in O(log n) time and
also prove its running time.
Thank you in advance

December 4th, 2015, 12:18 PM
#2
Re: Given an array that contains numbers from 1 to 1+n
I assume that this is homework, so I'll just give you some hints:
For (a) : use the fact that : 1 + 2 + 3 + ... + (n+1) = (n+1)*(n+2)/2
For (b) : do a binary search. Compare the array value at the current "mid" index
with the index itself.

December 4th, 2015, 01:35 PM
#3
Re: Given an array that contains numbers from 1 to 1+n
Originally Posted by Philip Nicoletti
I assume that this is homework, so I'll just give you some hints:
For (a) : use the fact that : 1 + 2 + 3 + ... + (n+1) = (n+1)*(n+2)/2
For (b) : do a binary search. Compare the array value at the current "mid" index
with the index itself.
Thank you for the replay that hhelped me alot I think I have now and idea how to do the (b), but still can't figure out the first one. I am still new to algorithms and have some omissions in my knowledges.

December 4th, 2015, 01:45 PM
#4
Re: Given an array that contains numbers from 1 to 1+n
Say N = 10 .. The array will have the numbers 1 thru 11 (with one missing)
1 + 2 + 3 + ... + 11 = 11(12)/2 = 66
Sum the elements in your array. It will be less that 66, since one number is missing.
Compare your sum with 66

December 4th, 2015, 02:08 PM
#5
Re: Given an array that contains numbers from 1 to 1+n
Thank you very much bro you helped me alot thumbs up
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
