CareerCup

Assume all this is in a function that returns true if a duplicate is found:

0) Needed is an abs. value function or macro:

#define ABS(x)  ( (x)<0?-(x):(x) )

1) Have a boolean flag to check if you have duplicate 0's.

bool seenzero;
for(i=0; i<N; i++)
	if( a[i] == 0 )
		if( seenzero ) return true;  //zero was seen before
	else	
		seenzero=true;

So the zero check is ~1n single pass, plus 1 boolean var. space.

Now we can assume the array has values in the range 1 to n-1 only.
This means a few things:
1) We can flip any value in the array from positive to negative and not "lose" information, because abs(a[i]) == original(a[i]) regardless if we flipped the sign.
So we can flip signs as we desire.
2) Since 0 can no longer be a value, we "know" if a[i] < 0, that "we" are the ones that had flipped it's sign. ( 0 would mess this up because -0 == 0 ).
3) Since the values are in the range 1 to n-1 and len(a)==n, all the original values of the array can index the array itself.

Now comes the code that someone has to do on paper to get it the first time:

for(int i=0; i<N; i++)
{
	// this means abs(a[i]) was used as an index into a[ ] already
	if( a[ abs(a[i]) ]  < 0 ) return true;  

	// first time abs(a[i]) used to index a[ ], change sign below to trap second time
	a[ abs(a[i]) ] *= -1;
}

return false; //neither the zerocheck or the self-indexing-sign-flipping caught the error

Type this raw, so hope it's okay.

Runtime O(n) , two passes with constant effort on each element during each pass
Aux. storage O(1) ... just the index i, and boolean seenzero (1 stack frame, registers)

Add 1 more pass if you need the array back to it's original form (take abs of each element).

//test the code
	public static void main(String[] args) {
		int [] 	array1 = {0,1,2,3,4,5};
		int [] 	array2 = {0,5,2,3,4,5};
		
		System.out.println("#1: "+duplicateChecker(array1));
		System.out.println("#2: "+duplicateChecker(array2));
	}


	/**You have an array of length n, containing values of length 0 to n-1.  Tell me if there exists a duplicate (return true or false).  Do it in constant space and O(n) time.*/
	public static boolean duplicateChecker(int[] array)  {
		int val;
		int len = array.length;
		
		boolean[] exists = new boolean[len];
		for (int i = 0; i < len; i++) {
			val = array[i];
			if (exists[val]) return true;
			exists[val] = true;
		}
		
		return false;
	}

This also should be "nondestructive" on the array.
* O(n) time
* O(1) space
* array left untouched after result returned

collabedit.com/bbptb

Again, no compiling/testing done.

#define ABS(x)  ((x)< 0 ? -(x) : (x))

/* put this in a function that return true if duplicate is found in array a[] of size N */

int zeropos = -1;  //position of any 0 found in array

for(i=0; i<N; i++)
    if(a[i] == 0) 
        if(zeropos != -1) return true; //duplicate 0 found (and array is untouched, so return immediately )
    else
        zeropos = i  //position of 0

a[zeropos] = 1;  //set to 1 so the next for loop works for dup="zeropos"

bool dupfound;    // true means we found duplicate 
for(int i=0; i<N; i++)
{
    // this means abs(a[i]) was used as an index into a[ ] already
    if( a[ abs(a[i]) ]  < 0 ) { dupfound = true; break; }  

    // first time abs(a[i]) used to index a[ ], change sign below to trap second time
    a[ abs(a[i]) ] *= -1;
}

/* next part "recreates" the original array */
for(int i=0; i<N; i++)
    if( a[i] < 0 ) a[i] *=-1;
    
a[zeropos]=0; //recreate the zero element

return dupfound;

The sum of first n numbers starting from 0,1,2, _ _ _ , n-1 is n(n-1)/2.
We can calculate the sum and then a for loop to calculate the sum of elements of array. If the two sums are not equal then return true else false. 

OverallComplexity O(n)

Basically, if there are no duplicates, we receive a permutation of the numbers 0..n-1.
We can rearrange the array such that number i is at position i.
Take this example: 0,3,2,5,4,1
0 is in the correct position.
3 is at position 1, we will swap it with the number at position 3 (5) to put it in the right position
0,5,2,3,4,1
now 5 is wrong, swap it with the number at position 5 (1)
0,1,2,3,4,5
now 1 is ok. 2, 3, 4 and 5 are too.

If at any step we try to swap a number into a position which already contains that number, then there are duplicates.

#include <iostream>
using namespace std;

bool Check(int* v, int n) {
	for (int i = 0; i < n; i++)
		if (v[i] != i) {
			do {
				if (v[v[i]] == v[i])
					return true;
				swap(v[i], v[v[i]]);	
			} while (v[i] != i);
		}
	return false;	
}
int main() {
	int v1[] = {0,1,2,3,4,5};
	int v2[] = {0,5,2,3,4,5};
	int v3[] = {0,3,2,5,4,1};
	cout << Check(v1, 6) << endl;
	cout << Check(v2, 6) << endl;
	cout << Check(v3, 6) << endl;
	return 0;
}

bool dup_exists(vector<int>& v)
{
	// this's order O(N) .. the both 
	// loop combined only iterate all element only once.
	for (int i = 0; i < v.size(); i++)
	{
		while (v[i] != i) 
		{
			int temp = v[v[i]];
			if (temp == v[i]) return true;
			v[v[i]] = v[i];
			v[i] = temp;
		}
	}
	return false;

}

public boolean solution(int[] list) {
	int[] solutions = new int[list.length];
	for(int i : list) {
		solutions[i] = 1;
	}
	for(int k : solutions) {
		if(k == 0) {
			return false;
		}
	}
	return true
}

for(i=0;i<n;i++)
{
sum=sum+arr[i];
sum=sum-(i+1);
}
if(sum==0)
printf("No duplicate element in array\n");
else
printf("duplicate element occure in array\n");

for(i=0;i<n;i++)
{
sum=sum+arr[i];
sum=sum-(i+1);
}
if(sum==0)
printf("No duplicate element in array\n");
else
printf("duplicate element occure in array\n");

How about using XOR:

a[n+1] = {0};
for(int i =0; i < n; ++i
{
	int k = array[i] + 1;	// add one is for the element zero
	if (a[k]^k == 0)	
		return true;
	else
		a[k] = k;
}

return false;

I just think of a way.
in C++, there is a "set" container.
it will only store unique value.

So go along the array and insert value into the container, with complexity O(n).
compare the size of this container and original array.
if they are the same, there are no duplicate.

It is not warranted that the array is sorted or if every element is placed in its correct index within the specified range. We can still have an O(n) algorithm using XOR of the elements of the array. If the final XOR-ed value is zero that means all elements are of even number, so they cancel each other out. Otherwise, the result of this XOR is the element with no duplicate.

bool CheckDuplicate(int *a, int n)
{
if(a==NULL || n<=0)
 return false;
result=0;
for(i=0;i<n;i++)
  result^=a[i];
return (result==0 ? true : false);

return sum(a[i]) != n*(n+1)/2

Use xor