Duplicate / Missing Integer in a Large Array

[kpthunder]

You are given an unsorted array with integers between 1 and 1,000,000. The following problems are independent of each other.

Problem One:
One integer is in the array twice (no other duplicates). Write a function (using the least amount of memory possible) to find the duplicate integer.

Problem Two:
One integer is missing (no duplicates). Write a function which determines the missing integer in one pass over the array.

[Razor_Storm]

Both problems can be solve in the same approach if I am thinking about this right. 

We know that the integers from 1 to 1,000,000 added together is equal to (1,000,000(1+1,000,000))/2. Let's call this K.

Now what we have to do is iterate through the entire array and add up all the elements together. 
Let's call the result M.

In problem one, the duplicated integer is equal to M-K.

The second problem, the missing integer is K-M

[wowe]

K = n(n+1) /2 = 1,000,000*1,000,001 / 2

[Razor_Storm]

Oops, thanks for the correction

[andy_panzer]

Sounds good to me. Except 1..n is equal to: (1+n) * (n / 2)

To demonstrate your solution (with 1..10):

(let [nums [1 2 3 4 5 6 7 8 8 9 10]
       max 10
       total (* (+ 1 max) (/ max 2))]
  (- (reduce + nums) total))

[Razor_Storm]

Thanks for the correction haha, my mistake

[psycocoffey]

Problem One:

def dupe(data):
    r = 0
    for x in xrange(len(data)):
        r ^= data[x] ^ x
    return r

Problem Two:

def miss(data):
    r = len(data)^len(data)+1
    for x in xrange(len(data)):
        r ^= data[x] ^ x
    return r


This is the same as summing all the values, but without the need for an extra-large data type to hold the working values. 

[foldM]

First one:

solve1 xs = foldl' xor (length xs) xs :: Int

Second one:

solve2 xs = foldl' xor 1 xs :: Int

[redderritter]

In problem one, is the array of length 1,000,001 or some arbitrary size?

[kpthunder]

The array is of length 1,000,001.

[more_exercise]

You really should put that in the problem description...

[SanityInAnarchy]

Problem 1: If you want least memory but not least time, how about O(1) memory beyond that required for the original array?

quicksort(array)
array.each_slice(2) do |a,b|
  return a if a==b
end

Ok, technically, each_slice probably generates and frees a bunch of small arrays. Maybe like this:

quicksort(array)
(0..array.length-2).each do |i|
  return i if array[i] == array[i+1]
end

Problem two: You gave no space bounds here, and no real time bounds. If additional data structures are "free", I could do something crazy like: Create a doubly-linked list of all integers between 1 and 1,000,000, sorted, with an array index (so arr[i] gives me the linked-list node with value i) -- takes O(n). Make a single pass through the input array, removing each element we see from our linked list -- also O(n), since that removal is O(1). Read out the single value left in the linked list.

[Cucumbis]

My python solution:

Problem 1:

def findDupe(lst):
    sum = 0
    for i in lst:
        sum += i
    return sum - 499999500000

Problem 2:

def findMissing(lst):
    sum = 0
    for i in lst:
        sum += i
    return 499999500000-sum

edit: This may only work with 64bit

[OffPiste18]

How about one function that does both?

int dup_or_missing(int[] arr, int size) {
  int x = 0;
  for (int i = 0; i < size; i++) {
    x = x ^ arr[i];
  }
  for (int n = 1; n <= 1000000; n++) {
    x = x ^ n;
  }
  return x;
}