CareerCup

We will traverse array and will make a[abs(a[i])] negative if its +ve.. if a[a[i]] is already negative .. means no is repeated we will replace it with zero and so on .. o(n) ...

in next traversala we will remove all the zeros from the array and will make all -ve values +ve .. o(n)

o(n)+o(n) =o(n)

you cannot do it in O(1) space with O(N) time if there are more than one duplicated elements in the array. If there was one, i would just sum it up and get the difference from arithmetic series of 1..N

/* The question is find and delete duplicates in an array of size N with a max value N in time complexity O(N), and space O(1)
The time complexity of this program is O(2n + n +n ) = O(4n) i.e. O(n). Space complexity = O(1).
Assuming the input array can store an element of value '2n'.
From the problem we know that the elements range 1 to n so we place elements in their corresponding positions.

Pseudo code:
for each element a[i]
   if(a[i]==i+1 || a[i]>n)
      continue //i.e. either inplace or duplicate
   else
      while(true)
	   if(a[i]>n) //i.e. a duplicate that is already detected
		break
           if(a[a[i]-1]==a[i])
		a[i]+=n	//i.e. a duplicate is detected
		break
           swap a[i] and a[a[i]-1]
           if(a[a[i]-1]==a[i]) //i.e. swapped inplace
		break

Complexity analysis:
Consider for an element a[i], k elements are swapped. i.e. k elements are inplace.
which means each of these k elements require atmost 1 comparison i.e. O(k) and the max value k
can take is n-1 => O(n-1 + n) == O(2n) ==> O(n)
For example, element a[0], the worst case would be, doing a maximum swaps of (n-1) which
means that n-1 elements are in place. so for each of these n-1 elements we only do one comparison i.e. a[i]==i+1
Therefore, atmost 2n comparisons are made
Once we place all elements in place, all elements greater than n are duplicates,
move duplicate elements to the end, so parse once again and swap duplicates to the end.
=> Complexity = O(2n + n + n) = O(4n) ==> O(n)
Test case:

1 5 3 8 4 3 8 5 2 // i=0,
1 4 3 8 5 3 8 5 2 // i=1 swap a[1] and a[a[1]-1] i.e. swap '5' and '4'
1 8 3 4 5 3 8 5 2 // i=1 swap a[1] and a[3] i.e. swap '4' and '8',
1 5 3 4 5 3 8 8 2 // i=1 swap a[1] and a[6] i.e. swap '8' and '5',
1 14 3 4 5 3 8 8 2 // i=1 Since, a[5-1]==5 && a[1]==5, a[i]+=n => 14
1 14 3 4 5 3 8 8 2 // i=2, since a[2] = 2+1 do nothing
1 14 3 4 5 3 8 8 2 // i=3, since a[3] = 3+1 do nothing
1 14 3 4 5 3 8 8 2 // i=4, since a[4] = 4+1 do nothing
1 14 3 4 5 12 8 8 2 // i=5 Since, a[3-1]==a[i], a[i]=n+a[i] => 12
1 14 3 4 5 12 17 8 2 // i=6 Since, a[8-1]==a[i], a[i]=n+a[i] => 17
1 14 3 4 5 12 17 8 2 // i=7 Since, a[7]==8; //inplace so continue
1 2 3 4 5 12 17 8 14 // i=8 swap a[1] and a[8] i.e. swap '14' and '2'

//All duplicates are greater than n with a value a[i]-n i.e. 12,17,14 i.e. 3,8,5
*/

#include <iostream>
using namespace std;
//!Function to swap values, pass by reference
void swap(int *x,int *y){
	*x = *y + *x;
	*y = *x - *y;
	*x = *x - *y;
	cout<<"swapping '"<<*x<<"' and '"<<*y;
}

int main(){
	int a[] = {3,3,3,3,3,2,2,2,2,2,2,3,3,3,3,3,2,2,2,2,2,2,4};
	int n = sizeof(a)/sizeof(int);
	int numComparisons = 0;
	for (int i=0;i<n;++i){
		++numComparisons;
		if(a[i]==i+1 || a[i]>n)
			continue; 			//i.e. either inplace or duplicate
		else{
			while(i<n){
							++numComparisons;
				if(a[i]>n) 		//i.e. a duplicate that is already detected
					break;
				int u=a[a[i]-1];
				if (u==a[i])
				{ 
					a[i]+=n;	//i.e. a new duplicate is detected
					break;
				}
				cout<<endl<<"swapping a["<<i<<"] and a["<<(a[i]-1)<<"] i.e. ";swap(&a[i],&a[a[i]-1]);
				if(a[a[i]-1]==a[i])
					break;
			}
		}
	}

	//Move duplicates to the end, though there are two while loops, 
	//they break on a same condition i.e. when both pivots meet and 
	//pivots are ALWAYS MOVING INWARDS so the maximum number of iterations for these while loops together is N
	int endPivot = sizeof(a)/sizeof(int) -1;
	int beginPivot = 0;
	while(beginPivot<=endPivot){
		++numComparisons;
		if(a[beginPivot]>n){
			while(beginPivot<=endPivot){
				++numComparisons;
				if(a[endPivot]<n){
					swap(&a[beginPivot],&a[endPivot]);
					break;
				}
				--endPivot;
			}
		}
		++beginPivot;
	}
	//Final array
	cout<<endl<<"Final Array : ";
	for (int k=0;k<n;++k){
		cout<<a[k]<<",";
	}
	//Print duplicates
	cout<<endl<<"Duplicates are :: ";
	for (int i=beginPivot;i<n;++i){
		++numComparisons;
		if(a[i]>n)
			cout<<a[i]-n<<",";
	}
	cout<<endl<<"Number of comparisons"<<numComparisons<<endl;
}

Bloody hell. I'm not cut out for it.

I think the problem stmt intends to convey that the solution should have linear time complexity. So if the length of the array is m ,m could be >> N (a relatively small number)

Let's define this frequency array F[1...N] that would hold the frequencies of the element k in the original array A. So e.g. if N = 5, and the original array is
[2,1,3,1,1,1,3,5,2,4], the frequency array F would be [4,2,2,1,1]. Observe that regardless of the size of the original array, the size of F would always be the same. So F would actually occupy constant space for any value of m.

The algo now gets very simple. A single pass over the original array A

initialize the elements of F to zero
for (i=1...N){
if( F[a[i]] == 0){
F[a[i]]++;
}else{ // if we have already encountered the *value* a[i] in an earlier iteration
a[i]=NULL;
}
}

Run the above algo on [2,1,3,1,1,1,3,5,2,4]. At the end of the pass,the array become
[2,1,3,null,null,null,null,5,null,4], which is what's the goal ..enjoy !!

@above
wat absurd..!!

I don't know what is the problem if the array size is >N.
If size of array is m
for(i =1 to m){
a[a[i]]=a[i];
}
when size of array is smaller than N than
for(i=1 to m){
a[a[i]%m]=a[i];
}

If you need to preserve the order of numbers than we need to think more.

Visit coders-stop.blogspot.com/

@chenna
laundiya hoshihaar hai .....
machak !!

<pre lang="java" line="1" title="CodeMonkey50426" class="run-this"> int countVector = 0;
int length = 0;
for(int i = 0 ; i< 10 ; i++)
{
if((countVector & (1<<a[i])) != 0)
continue;
else
{
a[length++] = a[i];
countVector = countVector | 1<<a[i];
}
}

for(int i = 0 ; i<length ; i++)
cout<<a[i];
cout<<endl;</pre><pre title="CodeMonkey50426" input="yes">
</pre>

#include <stdio.h>

int main()
{
int a[]={1,2,2,3,3,3,4,5,6,6,9};

int counter, lastIndex;
int length = sizeof(a)/sizeof(int);

// Set 0 for duplicates
for(counter=1,lastIndex=0;counter < length;counter++)
{
if(a[counter] == a[lastIndex])
{
a[counter] = 0;
continue;
}
lastIndex=counter;
}

// Print the whole array
for(counter=0,lastIndex=0;counter<length;counter++)
printf("%d ", a[counter]);
printf("\n");

// Move the 0(s) to end of the list.
for(counter=1,lastIndex=0;counter<length;counter++)
{
printf("lastIndex=%d counter=%d\n",lastIndex,counter);
if(a[counter] == 0)
{
//Set the lastIndex for the firsttime.
if(lastIndex == 0) lastIndex = counter;
continue;
}
if(lastIndex == 0) continue;

a[lastIndex]=a[counter];
a[counter]=0;
//For the first time lastIndex will be set above..
lastIndex = lastIndex+1;
}

for(counter=0,lastIndex=0;counter<length;counter++)
printf("%d ", a[counter]);

getchar();
return 0;
}

void removeDups (int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i] != i)
        {
            if (a[a[i]] != a[i])
                swap (a[i], a[a[i]]);
        }
    }

    for (int i = 0, j = 0; j < n; i++, j++)
    {
        while (a[j] != j)
            j++;
        a[i] = a[j];
    }
    a[i] = '\0';
}

package org.com.array;
// Removing Duplicate item from the array
public class P3
{
 static void duplicate(int a[])
 {
	 int t= a.length;
	 int index=0;
	 for(int i=0;i<t;i++)
	 {
		 for(int j=i+1;j<t;j++)
		 if(a[i]==a[j])
			 index=i;
		    }
	 for(int i=index;i<t-1;i++)
	 {
		 a[i]=a[i+1];
		     
	 }
	t--;
	 for(int i=0;i<t;i++)
		 System.out.print(a[i] + " ");
 }
	
	public static void main(String[] args)
	{
		int a [] ={1,2,3,4,2,6,7,3,9,10,10};
		duplicate(a);
	
		

	}

}

package org.com.array;
// Removing Duplicate item from the array
public class P3
{
static void duplicate(int a[])
{int t= a.length;
int index=0;
for(int i=0;i<t;i++)
{ for(int j=i+1;j<t;j++)
if(a[i]==a[j])
index=i;}
for(int i=index;i<t-1;i++)
{a[i]=a[i+1];}
t--;
for(int i=0;i<t;i++)
System.out.print(a[i] + " ");}
public static void main(String[] args)
{int a [] ={1,2,3,4,2,6,7,3,9,10,10};
duplicate(a);}}

package org.com.array;
// Removing Duplicate item from the array
public class P3
{
 static void duplicate(int a[])
 {int t= a.length;
	 int index=0;
	 for(int i=0;i<t;i++)
	 { for(int j=i+1;j<t;j++)
		 if(a[i]==a[j])
			 index=i;}
	 for(int i=index;i<t-1;i++)
	 {a[i]=a[i+1];}
	t--;
	 for(int i=0;i<t;i++)
		 System.out.print(a[i] + " ");}
	public static void main(String[] args)
	{int a [] ={1,2,3,4,2,6,7,3,9,10,10};
		duplicate(a);}}