CareerCup

WE CAN have an array of n elements and then check

func(int Original[])
{
int arr[n];
for (i=0;i<n+m;i++)
{
if (arr[Original[i]]>=0)
printf ("\n Repeated element is %d",Original[i])
else
arr[Original[i]]=1;
}

Comments and more efficient codes are welcome

Your code Space Complexity is: O(n) not O(m)

Since we know there are 1-n elements, we can sort the array in O(n). The first n elements will be the unique values and n to m will be the duplicates. This is O(n+m) && no extra space required.

for (int i = 0; i < array.Length; i++)
                {
                    if (array[i] != i + 1)
                    {
                        int t = array[array[i]-1];
                        array[array[i]-1] = array[i];
                        array[i] = t;
                    }
                }

here is the corrected version

func(int Original[])
{
int arr[m];
for (i=0;i<n+m;i++)
{
if (arr[Original[i]]>=0)
printf ("\n Repeated element is %d",Original[i])
else
arr[Original[i]]=1;
}

since n > m, so, for some Original[i] = n -1, arr[n-1] would be out of arr! wouldn't work.

none of above solutions will work according to me or else if they are working could you please explain how?

I try it! java ~

public fun(int[] a){
		
		BitSet bs = new BitSet(100);
		for(int i = 0;i<a.length;i++){
			if(bs.get(x[i])){
				System.out.println(x[i]);
			}
			bs.set(x[i], true);
		}
             }

public fun(int[] a){
		
		BitSet bs = new BitSet(100);
		for(int i = 0;i<a.length;i++){
			if(bs.get(a[i])){
				System.out.println(x[i]);
			}
			bs.set(a[i], true);
		}
             }

int[] findDuplicates(int[] a , int n, int m){ //size of a is n+m
int dup[] = new int[m];
int i =0 , j= 0;
for(;i<n+m;i++){

if(a[a[i]-1] > (n+1)){ //a[i] is occurred already i.e duplicate
dup[j++] = a[i]
}else{ //add (n+1) when u encounter an element first time;
a[a[i]-1] += (n+1);
}
}
return dup;
}

Please people, do write a word or two about what the approach is rather than just dumping the code !
Case if space complexity of O(n) is straight fwd. Only ....

If this array is a sorted one, it is possible.
If Not, a hash table (max m items) can be used, or use the m space in the array to simulate a hashtable operations.

3rd Post by Anonymous is the correct one.

All we need to do is put the elements at its corresponding index and the duplicates will be pushed to the end...So the first 'n' will the unique values and the next 'm' will be the duplicates.

the solution/approach by Anonymous is the correct and rest Junk!

Algorithm:
1. Move Left to Right, Swap element if not at right position.
2. Move Right to Left, Swap element if not at right position.
3. Take last m position as result.

Let Input is 5 3 1 2 2 4 5
Array
Left to Right
5 3 1 2 2 4 5
2 3 1 2 5 4 5
2 1 3 2 5 4 5
2 2 3 1 5 4 5
2 2 3 1 5 4 5
2 2 3 4 5 1 5
2 2 3 4 5 1 5

Let Input is 2 2 3 4 5 1 5
Right to Left
2 2 3 4 5 1 5
2 2 3 4 5 1 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5

Result 2, 5

Algorithm:
1. Move Left to Right, Swap element if not at right position.
2. Move Right to Left, Swap element if not at right position.
3. Take last m position as result.

Let Input is 5 3 1 2 2 4 5
Array
Left to Right
5 3 1 2 2 4 5
2 3 1 2 5 4 5
2 1 3 2 5 4 5
2 2 3 1 5 4 5
2 2 3 1 5 4 5
2 2 3 4 5 1 5
2 2 3 4 5 1 5

Let Input is 2 2 3 4 5 1 5
Right to Left
2 2 3 4 5 1 5
2 2 3 4 5 1 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5

Result 2, 5

Algorithm:
1. Move Left to Right, Swap element if not at right position.
2. Move Right to Left, Swap element if not at right position.
3. Take last m position as result.

Let Input is 5 3 1 2 2 4 5
Array
Left to Right
5 3 1 2 2 4 5
2 3 1 2 5 4 5
2 1 3 2 5 4 5
2 2 3 1 5 4 5
2 2 3 1 5 4 5
2 2 3 4 5 1 5
2 2 3 4 5 1 5

Let Input is 2 2 3 4 5 1 5
Right to Left
2 2 3 4 5 1 5
2 2 3 4 5 1 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5
1 2 3 4 5 2 5

Result 2, 5

any idea abt deepaks solution it seems correct to me

deepak's solution is OK.
in the first shuffle [left to right] you partially sort the numbers in increasing order and the second step is the crucial one[right to left], in this step you actually put the numbers 1-n in their actual position pushing the duplicates to the end and that gives the required result.

This can be done in O(n+m) time without using any space .
here is the pseudo code :-

for i->1 to m+n {
  a[a[i]%n]+=n
 } 

for i->1 to n {
  print "number i occurs "  a[i]/n "times
}

for example :-
take n=4
input :-
2,1,3,3,4,1,2

when i=1
2,5,3,3,4,1,2
i=2
6,5,3,3,4,1,2
so on final array :-
10,9,11,7,4,1,2

hence 1 occurs 10/4 = 2 times
'' 2 occurs 9/2=2 times
'' 3 occurs 11/4=2 times
4 occurs 7/4 = 1 times

I think the following algorithm is incorrect

Algorithm:
1. Move Left to Right, Swap element if not at right position.
2. Move Right to Left, Swap element if not at right position.
3. Take last m position as result.

Counter Example:

Left->Right

5 4 6 6 2 1 3
2 4 6 6 5 1 3
2 6 6 4 5 1 3
2 6 1 4 5 6 3
2 6 3 4 5 6 1

Right->Left
1 6 3 4 5 6 2

The output is 2, which is wrong.

524638917184
324658917184
423658917184
623458917184
823456917184
123456987184
123456789184

1, 8 , 4 are repeated...:)
Looks good to me..

Sorry dowsnt work....

512464389817
612454389817
412456389817
4 and 4 ....Mov ahead
142456389817
again 4 and 4 move ahead
124456389817
again 4 and 4 move ahead..twice
123456489817
123456789814 814 are repeated....

will come up with an algp but this works

public static void getRepeatedVariables(int [] array, int n) {
int m = array.length - n;
int i = 0;
while(i < array.length) {

swap(array, i, array[i]);
if(array[i] == i)
i++;

if(array[i] == array[array[i]])
i++;

printArray(array);
}

}

int i = 1;
while (i <= N + M)
{
if (arr[arr[i]]!=arr[i]) swap(arr[arr[i]],arr[i]);
else ++i;
}

I start my solution by virtually partitioning the array into n followed by m elements. The last m elements will give the duplicates, while the first n elements will contain partially sorted, in place, first n elements.

for(i=m; i<m+n; i++)
{
curr = a[i];

/* traverse as long as we have no duplicate setting each element n to its position at a[n]*/
while(a[curr] != curr)
{
temp = a[curr];
a[curr] = curr;
curr = temp;
}

/* set the duplicate found to a[i] and move on */
a[i] = curr;
}

At the end, many of the first n elements will be sorted in their correct spot such that a[n]==n. Some will remain unsorted, but they will still be no duplicates, just shuffled away from their proper location because they were never hit by the bubbling process. The m elements at the end are constructed to be duplicates.

Note, the complexity is O(m+n). Even though it appears that for each of the m elements we could do n operations, however, it is an amortized analysis because we only do at most a complete pass across the n partition while processing all the m duplicates.

Thanks!

We know each number between 1-n must appear once, with one number appearing m times. We know the sum of the numbers between 1-n sum(n) = ((n+1)(n))/2. The calculated sum will be real_sum(arr) = ((n+1)(n))/2 + (m-1)(x) for some x repeated m-1 times. We can therefore calculate the value that is repeated through simple math. num = (sum - real)/(m - 1). n will be the maximum value in the array and sum will be the sum of the elements in the array, both done in one loop O(n+m). Calculation is O(1) and we're done.

int n = 0;
		int s = 0;
		for (int i = 0; i < arr.length; i++) {
            n = (arr[i] > n ? arr[i] : n);
            s += arr[i];
        }
		
		int e = ((n+1)*n)/2;
		int num = (s - e) / (arr.length - n);

Given an array A that is assumed to start with index 1.

Consider A[1]. Swap A[1] with A[A[1]] if A[A[1] != A[1],
Only when you can cannot swap which is when A[A[1] = A[1], you proceed to next index in the array A[2] and so on and so forth. This means you have found the duplicate.

Once you are done with the array, you would be left with A[1..n] unique elements and A[n+1..m] duplicates.

#include<stdio.h>

int main ()
{
int n = 9,m = 12;
int arr[12] = {9, 9, 9, 6, 5, 4, 3, 2, 1, 7, 8, 9};
int i,j,temp,curr;

for(i=0;i<m;i++) {
printf("%d : ",arr[i]); }

for(i=0; i<m; i++) 
{
curr = arr[i]; 
if((i+1) != curr)
{
temp = arr[curr-1];
arr[curr-1] = arr[i];
arr[i] = temp;
}
}

printf("\n");
for(i=n;i<m;i++)
printf("%d : ",arr[i]);

return 0;
}

Above alg failed at this case
int n = 9,m = 10;
int arr[10] = {6, 9, 5, 1, 4, 8, 3, 2, 7, 7};

6 : 9 : 5 : 1 : 4 : 8 : 3 : 2 : 7 : 7 :
4 :

How come no one mentioned the "negate" approach? For each a[i], which we know is between 1 and n, check if a[a[i]] is negative. If not, set it to negative to indicate that we just seen a[i]. If it is negative, we know a[i] is a repeated number. Use a separate array to keep the m repeated elements, hence the O(m) space constraint. At the end, traverse the array and undo the negations to restore the array.