CODEWITHSUNDEEP
algorithmdata-structuresbig-o
user1049336
user1049336

Reputation: 29

O(n) algorithm, find the missing integer

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

need some help for this question,

Upvotes: 0

Views: 3176

Answers (3)

gusbro
gusbro

Reputation: 22585

Here goes another approach:

  1. Set a temporary variable Number with 0
  2. For each element in array, set Number = Number XOR element
  3. For each number M, M > N and M < 2**(ceil(log2(N)) set Number = Number XOR M
  4. Missing number is Number

Upvotes: 0

Kwariz
Kwariz

Reputation: 1316

Use an additional tmp variable initialized with -1, then kind of sort the array in place using tmp as position n :

function find_missing(array)
begin
  tmp := -1
  i := 0;
  while i<length(array)
    if (array[i] = -1) or (array[i] = i) then
      // either on a cell with the right number or 
      // a candiate for the missing number, just go on
      i := i + 1
    else if array[i] = n then
      // use tmp as the nth cell
      array[i]=tmp
      tmp=n
    else
      // swap the value of the current cell with the value
      // of the cell were the value i should be
      swap(array, i, array[i])
    end if
  end while
end

-1 should point to the missing number.

Upvotes: 1

amit
amit

Reputation: 178451

  1. Sum the array.
  2. Calculate the expected sum using arithmetic progression formula

Given these values: one is 0 + 1 + 2 + ... + n-1, the other is the sum of your actual elements - think how they differ from each other, what does one have that the other does not. Make sure you know it, and the answer is trivial.

EDIT: (Theoretical comment):
Note that sum(array) needs 2*log_2(max(arr)) bits. So, if your elements are all 32 bits integers, you are going to need at most 64 bits to represent the sum.
From purely theoretical approach - it is NOT O(1). However, you can use the array itself (It contains more then 2*log_2(max(arr)) bits) to store the sum.

Upvotes: 5

Related Questions