7

Possible Duplicate:
Easy interview question got harder: given numbers 1..100, find the missing number(s)
Find the missing and duplicate elements in an array in linear time and constant space

I saw an interesting Question on one forum.

you have 100 elements from 1 to 100 but byy mistake one of those number overlapped another by repeating itself. E.g. 1,99,3,...,99,100 Array is not in sorted format , how to find the repeating number ?

I know Hash can do it O(n) time and O(n) space, I need O(1) space.

Community
  • 1
  • 1
user973931
  • 515
  • 1
  • 4
  • 13

4 Answers4

24

Calculate two sums: sum and square sum.

In your example:

sum = 1+99+3...+100

sq_sum = 1^2+99^2+3^2+...+100^2

Assume y replaced x in the sequence. 

sum = n(n+1)/2 -y+x.
sq_sum = n(n+1)(2n+1)/6 -x^2 +y^2

Now, solve for x & y.

Constant space and O(n) time.

How to solve for x and y

From equation:

x = sum - n(n+1)/2 +y

Substitute this in the second equation:

sq_sum = n(n+1)(2n+1)/6 -(sum - n(n+1)/2 +y)^2 +y^2

Note that y^2 cancels and you are left with a linear equation with only one unknown:y. Solve it!

svick
  • 236,525
  • 50
  • 385
  • 514
ElKamina
  • 7,747
  • 28
  • 43
  • 2
    This answer has 2 down votes and no comments. Please explain what is incorrect here so that the OP can rebut or revise and others understand the (potential) problem. – PengOne Jan 31 '12 at 00:52
  • How do you solve this for x&y? – WisaF Jan 31 '12 at 01:15
  • is square sum really needed, if the array length is 101 and there's 100 unique values, then you sum those 100 unique values and get 5050, the suppose the sum comes back as being 5149 you instantly know that 99 was duplicated, this doesn't work when there are more than one duplicates but the question only mentioned one value repeated once. – Seph Jan 31 '12 at 09:03
  • @Seph Array length is 100. One number is repeated, one number is omitted. Hence two unknowns, requiring two equations. – Nick Barnes Jan 31 '12 at 10:21
  • Why would anybody downvote a correct answer? – TT_ stands with Russia Jan 11 '14 at 18:19
  • The space required for `sum` and `sq_sum` is dependent on the input size, i.e. not constant space – Justin Bell Aug 15 '17 at 01:25
4

New approach. Let m be the missing number and r be the repeated number. Passing through the array once, let X be the result of XORing the entries of the array along with the indices 1 to n. Then X = m XOR r. In particular, it isn't 0. Let b be any nonzero bit of X (you only need to choose one, and one exists since X is not 0). Passing through the array, let Y be the result of XORing the entries of the array and the indices 1 to n where the bit b is 0 and let Z be the result of XORing the entries of the array and the indices 1 to n where the bit b is 1. Then Y and Z hold m and r, so all that remains is to make a final pass to see which is in the array.

Total space: 4 (or 3 if you reuse X for b)

Total time: 7 passes (or 3 if you do indices at the same time as the array and compute Y and Z at the same time.

Hence O(1) space and O(n) time.

PengOne
  • 48,188
  • 17
  • 130
  • 149
  • Are you sure? In the first step slow is n+1. So array[slow] returns error or garbage, no? – ElKamina Jan 31 '12 at 01:00
  • 1
    I still think it wouldn't work. Consider cases where there are multiple cycles. Or consider a case where array[n]=n. – ElKamina Jan 31 '12 at 01:06
  • So you need one extra passes for each non-zero bit of X right? In that case your solution O(nlogn) in time. I am not very sure of that fact, but please let me know. – ElKamina Jan 31 '12 at 01:42
  • @ElKamina No, you only make one pass for your favorite nonzero bit. You do not have to do this for every nonzero bit. It works for any nonzero bit. – PengOne Jan 31 '12 at 01:43
  • 1
    Does size of X depend on n? If yes, then it's not O(1) space. – TT_ stands with Russia Jan 11 '14 at 18:33
1

We can do it in O(n) and constant space:

  1. For every element, calculate index = Math.abs(a[i]) - 1
  2. Check the value at index
    • If it is positive, multiply by -1, i.e., make it negative.
    • if it is negative, return (index+1) as answer, as it means we have seen this index before.

""

static int findDup(int[] a){
    for(int i=0;i<a.length;i++){
        int index = Math.abs(a[i]) - 1;
        if(a[index] < 0)
            return index+1;
        else
            a[index] = -1 * a[index];
    }
    return -1;
}
CommonMan
  • 3,868
  • 2
  • 24
  • 35
  • But what if the values in the array exceed the bounds of the array, e.g. 1000, 1001, 1002, 1000, ... – schtever Jan 31 '12 at 00:08
  • The question clearly said its 1 to 100 and one element is repeated. – user973931 Jan 31 '12 at 00:09
  • Yup - I should read more carefully :/ – schtever Jan 31 '12 at 00:11
  • @schtever yes this will NOT work for that but as user973931 said the question states clearly that numbers are 1 to 100. – CommonMan Jan 31 '12 at 00:11
  • 10
    You're storing a piece of information for (potentially) every element in your input. This is not constant space. – Nick Barnes Jan 31 '12 at 00:19
  • @Nick Do you understand what is space complexity? :) – user973931 Jan 31 '12 at 00:22
  • @user973931 Sorry, meant to say "constant space", not "O(n) space" (edited). – Nick Barnes Jan 31 '12 at 00:29
  • 1
    @Nick Why you think its not constant space? I am using the same array for storing -ve sign – CommonMan Jan 31 '12 at 00:31
  • 6
    @Manan You're still using a linear amount of space to construct your solution. If your input set is immutable, or not randomly accessible, or doesn't support signed integers, then you'd need to create this array yourself. – Nick Barnes Jan 31 '12 at 00:33
  • @Nick The answer is applicable only with the constraints given in questions..... – CommonMan Jan 31 '12 at 00:35
  • 9
    @Manan None of these constraints (modifiable signed input with constant-time random access) was explicitly given in the question, so it's a bit of a stretch to assume them. But in any case, this still doesn't qualify as a constant-space algorithm. It's not a question of how many bytes you need to malloc(); it's a question of how many pieces of information you need to record. – Nick Barnes Jan 31 '12 at 00:49
  • @Elkamina thanks but I think the question clearly states that the numbers are b/w 1 to 100 and have exactly one overwritten by some other... I would appreciate if you can correct me where am I going wrong... Thanks again – CommonMan Jan 31 '12 at 00:52
  • @Manan Your solution requires storing n extra values (n=100 here), because you are storing index. That is not constant space solution. – ElKamina Jan 31 '12 at 00:55
  • @Elkamina I think you got me wrong I am not storing any index.. The index in the code above is a temporary variable.. For Clarity I have posted the code above – CommonMan Jan 31 '12 at 01:03
  • 1
    @Manan But you're still storing something. Your algorithm is basically a bucket sort. Your buckets in this case are the vacant sign bits in your input array. But it's still a linear-space algorithm. – Nick Barnes Jan 31 '12 at 01:09
  • 2
    @Manan The line `a[index] = -1 * a[index];` overwrites the input. This is why people are stating that this solution is not constant space. – PengOne Jan 31 '12 at 01:10
  • @Elkamina, believe me if you run my code above the given example[5 5 3 2 1] will work. – CommonMan Jan 31 '12 at 01:14
  • @Manan My apologies. Yes, it does work. But, since you are mutating the array, it is still not a valid O(n) solution. – ElKamina Jan 31 '12 at 01:36
  • @Manan Let me give you an example where it won't work. Let us assume I am working on this weird 7 bit computer and the input is an array on 7 bits. Essentially, you are assuming that there is enough room to store one extra bit of information. – ElKamina Jan 31 '12 at 04:11
  • @Elkamina ok this will NOT work there... But do you think summation will work.. what if sum goes out of range? To add to it you are doing sum of squares too :) – CommonMan Jan 31 '12 at 17:58
  • @Manan You don't need to store multiple sums of multiple sum of squares. But just one instance of each. That is different than one extra bit for *every* number in the array. Anyways, see PengOne's solution below. Unarguably that is the best solution to this problem. – ElKamina Jan 31 '12 at 18:47
-1

Calculate Sum of all integers Calculate int p = sum % 100 100 - p is the answer

topcoder
  • 15
  • 2