Find repeating in O(n) and constant space [duplicate]

Question

This question already has answers here:

Closed 13 years ago.

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.

• TT_ stands with Russia: Why did you accept incorrect answer? (not O(1) space)

Answer 1

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!

• PengOne: 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.
• WisaF: How do you solve this for x&y?
• Seph: 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.
• Nick Barnes: @Seph Array length is 100. One number is repeated, one number is omitted. Hence two unknowns, requiring two equations.
• TT_ stands with Russia: Why would anybody downvote a correct answer?

Answer 2

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.

• ElKamina: Are you sure? In the first step slow is n+1. So array[slow] returns error or garbage, no?
• ElKamina: I still think it wouldn't work. Consider cases where there are multiple cycles. Or consider a case where array[n]=n.
• ElKamina: 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.
• PengOne: @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.
• TT_ stands with Russia: Does size of X depend on n? If yes, then it's not O(1) space.

Answer 3

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;
}

• Nick Barnes: You're storing a piece of information for (potentially) every element in your input. This is not constant space.
• CommonMan: @Nick Why you think its not constant space? I am using the same array for storing -ve sign
• Nick Barnes: @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: @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.
• PengOne: @Manan The line a[index] = -1 * a[index]; overwrites the input. This is why people are stating that this solution is not constant space.

Answer 4

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

• Nick Barnes: This will only give you the difference between the missing number and the duplicated one, but not enough to identify either of them. You've got two unknowns, you need to equations. See ElKamina's answer above.
• ElKamina: That is incorrect. Take two cases: 5 is replaced by 10 and 6 is replaced by 11. In both cases sum is going to be the same.
• topcoder: example 1,99,3,4...100. Now sum % 100 will be 98. 100-98 is 2 :)
• PengOne: @topcoder I get 1+99+3+4+...+100 % 100 = 47.
• PengOne: @NickBarnes The sum of 1 to 100 modulo 100 is not 0. Why does everyone think that it is? 1+2+...+100 = 5050!!