CareerCup

Hope it'll work!!
if the array size is n and the array elements are in the range 1 to n-1(with one element repeated) then we will traverse the array once from index(0) to index(n-1). If we have k at index(0) make the array value negative at index k(if positive) else return that index if the value at that index is already negative.Will do the same for complete loop(while accessing the index ignore the sign of array element) until we get the repeated element.

Thus no extra space is required and it'll take O(n) space. But we are loosing the original array here so no need to worry, just make all the negative elements of the array as positive in another pass.

ex. there is an array of size 5 with the values as-

A = [1,4,3,2,1]

for i = 0 A[0] = 1 so we will change A[1] which is +ve, now A = [1,-4,3,2,1]
for i = 1 A[1] = -4 so we will change A[4] which is +ve, now A = [1,-4,3,2,-1]
for i = 2 A[2] = 3 so we will change A[3] which is +ve, now A = [1,-4,3,-2,-1]
for i = 3 A[3] = -2 so we will change A[2] which is +ve, now A = [1,-4,-3,2,-1]
for i = 4 A[4] = -1 so we will change A[1] which is already -ve so report this index(1) as ans.

So every element is unique except for a single element that is present twice?

what is the range of data?

Who asked you this question? It's impossible. Did you ask him for more clarification?

To find 2 elements with same value in an arbitrary array will take O(nlogn) time. This is a research result. Infact it says if an element occurs k times in an array, searching duplicacy takes O(nlog(n/k)) asymptotically. That's why for majority element(k>n/2) we get O(n) solution.

There has to be some glitch, like elements are between 1 to n or something.

And since its said find duplicate element, should we consider that the element is a number?

if we consider that the elements are number and the array of size n contains all elements from 1 to n with one element appearing twice.

Let the element appears twice is i,

∑x = n(n+1)/2 = 1+2+3+4+5+...+i+...j+...+n

∑x^2 = n(n+1)(2n+1)/6 = 1^2+2^2+3^2+4^2+5^2+...+i^2+...j^2+...+n^2

Let the sum of the array be S
S = 1+2+3+...+i+...+i+...+n

Let
S2 = 1^2+2^2+3^2+...+i^2+...+i^2+...+n^2
Let this i replace element j.

∑x - S = j - i = ∂

∑x^2 - S2 = j^2 - i^2 = ß

so (j+i) = ß / (j - i) = ß / ∂

so 2j = ∂ + (ß / ∂)

The missing number = j = (∂ / 2) + (ß / (2∂))

This way we can find the missing number in O(n) time by traversing the array once.

If we can assume the array is of integers (or char), then we can use bit vector to find the duplicate in O(n) time and ~O(1) i.e. using just one extra integer.

I have come across this question before from Microsoft, we have decide some way to answer this impossible question.

Unemployed cannot be fired so easily ,say you have 500 terabytes of numbers? with 512 mb of space you can find out duplicates in O(n).

Guys for one I am sure this cannot be solved the way it is stated,I am suggesting we can ask Gayle Laakmann McDowell to settle this once and for all.

Are the elements within a range, say from m to n and all the elements are present and only one is duplicated?

Range lies between m and n
1. Swapping current number with its appropriate index so that number is at coorect place when sorted
2. if swapped index(computed k) itself contains same number. report such number duplicate
3. else swap numbers
4. move index if swapped index points to current index

i = 0
D()
	while(i <= n-m)
		k = a[i]-m
		if(k != i)
			if(a[k] == a[i])
				print a[i] as duplicate
				return
			else	
				swap(k, i)	
		if(k == i)
			i++

They never said not to change the array. So, why not sort the array and look for 2 adjacent elements that are the same?
Merge sort would do an in-place sort. The second phase is straight forward. Just a thought.

I assumed the array contained integers in the range {1..n} and one number was missing.
O(n) = n....

let a,b,c,d,a.

s=xnor(a,b,c,d,a) ------ O(n)

check s xnor a == 0 then a is the duplicate,
else check s xnor b == 0 and so on.

Question is correct... solution using xnor is correct

If We are OK with the extra Space then we can choose BST for finding Duplicate Element.

The problem can only be solved in O(n) time when all numbers are within range [n, m] where n < m where n and m can be either negative or position, and (m - n) / 2 >= half of integer range (in Java, it's Integr.MINIMUM, Integer.MAXIMUN inclusive. When these two conditions are met, here are the steps to solve it:

1. Scan the array to find the n and m.
2. Scan the array again minus n from every number: array[i] -= n. After this scan, all numbers >= 0.
3. Scan the array again to do
array[array[i]]

This could be one solution ::
Make a BST of the given set {O(logn)}. Now we can perform sorting operation in BST {O(logn)}. can find all the duplicate numbers.

T(n)=O(logn)+O(logn)=O(logn)[which in the worst case would tend to O(n)];

anonymous answer posted on nov. 20 1011 is good but do we have to do multiplication ? let there n numbers in the range of 1 to n and the number b occurs twice . the numers are stored in the array 'a'. then

sum1 = 0;
sum2 = n(n+1)/2;
for(int i=0; i<n; i++){
sum1 = sum1+a[i];
}
result = sum2-sum1;

if there is anything wrong then please notify. all constructive comments are welcome

I think this should be correct program.
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

For example, let n be 7 and array be {1, 2, 3, 1, 3, 6, 6}, the answer should be 1, 3 and 6.

Implementation:

#include <stdio.h>
#include <stdlib.h>
 
void printRepeating(int arr[], int size)
{
  int i;
  printf("The repeating elements are: \n");
  for (i = 0; i < size; i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}
 
int main()
{
  int arr[] = {1, 2, 3, 1, 3, 6, 6};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Looks quite easy: we just store 2 vars-bit-vectors ( for +ve an -ve values).
O(n) complexity and O(1) space

public static int Dublicate (int [] A)
{
	int positive = 0;
	int negative = 0;

	for (int i = 0; i < A.Length; i++)
	{
		if (A[i] < 0)
		{
			if (((negative >> Math.Abs(A[i])) & 1) == 1)
				return A[i];
			else
				negative |= 1 << Math.Abs(A[i]);
		}
		else
		{
			if (((positive >> A[i]) & 1) == 1)
				return A[i];
			else
				positive |= 1 << A[i];
		}
	}
	return int.MinValue;
}

The question is completely ...incomplete.
to answer this question in O(n) range must be specified.

The preson who posted this question is crazy and he is bit poor in algos.
dont waste our time by posting partial questions.
Thanks

make me wrong if i am??
we can use the property of XOR
if we have 4 number a,b,c,a
xor till three element sum = a^b^c
then xor this result with fourth element a^b^c^a which result = b^c
then again xor this by sum so let sum2 = sum^b^c = a
check if fourth element = sum2
then duplicate found
else
do next iteration

The question is completely ...incomplete.
to answer this question in O(n) range must be specified.

The preson who posted this question is crazy and he is bit poor in algos.
dont waste our time by posting partial questions.
Thanks