dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Given an array that contains numbers from 1 to 1+n

  1. #1
    Join Date
    Dec 2015
    Posts
    3

    Exclamation 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 worst-case 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

  2. #2
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,716

    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.

  3. #3
    Join Date
    Dec 2015
    Posts
    3

    Re: Given an array that contains numbers from 1 to 1+n

    Quote Originally Posted by Philip Nicoletti View Post
    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.

  4. #4
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,716

    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

  5. #5
    Join Date
    Dec 2015
    Posts
    3

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)