CareerCup

Since the Question says that array contains only +ve numbers(and that too from 1 to N), we can use the original array itself to keep track of the numbers that have been visited. This can be done by making the entry at any index -ve whenever we encounter any element while traversing it. At the end values at all the indexes will be -ve except the missing number.

Time complexity: O(N)
Space Complexity: O(1)

Here is the C method to do the same:

void remove_duplicates(int *arr, int size)
{
        int i;
        int sum = 0;
        int missing, repeated;
        REP(i,1,size)
        {
                int idx = arr[i];
                if(idx<0)idx *= -1;
                if(arr[idx]<0)
                {
                        repeated = abs(arr[i]);
                }
                else arr[idx] = -arr[idx];
        }
        REP(i,1,size)
        {
                if(arr[i]>0)
                {
                        missing = i;
                        break;
                }
        }
        printf("Repeated: %d\nMissing: %d\n",repeated, missing);
}

Hope that helps!!!

The above does not work because there is a repeated number.

There is nothing said like numbers will be from 1 to n in sorted order. It can be in any order

int sum=0,sqsum=0;
for(int i=0;i<n;i++){
   sum+=a[i];
   sqsum+=sqsum+a[i]*a[i];
}

Now [n*(n+1)/2]-sum=Missing no - Repeated no
[n*(n+1)*(2n+1)/6]-sqsum=Missing no^2 - Repeated no^2...now solve for missing and repeated no:s and traverse the array to find out the ans...O(n) time O(1) space

The following algorithm has O(n) time complexity and O(1) space complexity. Let the number that was repeated be x and the number that was missed be y.

a) Since, n is given, we calculate sum of numbers, requiredsum = n(n+1)/2
b) We add all the numbers in the array to get givensum.

Now, requiredsum = givensum - x + y. Hence y - x = requiredsum - givensum.

c) Calculate the product of all numbers, requiredproduct = n!
d) Multiple all the elements in the array to get givenproduct which is (n! * x)/y

Now, (requiredproduct * x) / y = givenproduct. So, x = givenproduct * y / requiredproduct.

Substitute in original equation to get the value of y.

If no space issue, we can just use index array (say idx), initialize it to ZERO.
then for each element in array (Say a), increment index array. At the end, index with ZERO value is missing (And index with value 2 is repeated).

idx[n]={0};
for(i=0;i<n;i++)
idx[a[i]]++;
for(i=0;i<n;i++)
{
if(idx[i]==0) printf("%d is missing",i);
else if(idx[i]==2) printf("%d is repeated",i);
}

compute sum, y-x = sum - n*(n+1)/2
compute sum of squared y^2 - x^2 = sum of squared - n*(n+1)*(2*n+1)/6

from there you would know x and y

Let x be the missing number which is repeated and y be the repeated number.
If you XOR all the numbers int the array and subtract if from n(n+1)/2 you will get x+y
If you add all the numbers in the array and subtract if from n(n+1)/2 you will get x-y
Then solve the 2 simultaneous equations.

Let n=3
A[1,2,1]
1 is repeated twice and 3 is missing.
n(n+1)/2 = 6
XOR A =2
x+y=4
Solving we get both missing number and repeated number.
Add A = 4
x-y=2

We can use xor for this problem..
For eg:
let n be 3 and the given numbers be 1 2 2
Let y = (xor all the numbers from 1 to 3) xor (xor all the given numbers)
so y would be the missing number xor the repeated number (3 ^ 2)
let i be the last set bit in y

xor all the numbers from 1 to n and numbers in the given set whose ith bit is set. xor this number with y, this would give either missing number or duplicated. is the number we got here is not in the array then it is the missing number or this is the duplicated number. we get the missing number by xoring this number with y..

comments pls..

Here's a O(n) without any extra space and without multiplication or addition (because factorial requires special datatype/datastructure)

// since we know there are n numbers in an array of size n all we want is to swap the numbers to their corresponding positions i.e. move '1' to 0th position, move '2' to 1st position ...etc.
if the number already exists in its position then its a duplicate and we set it to (n+1) or -1 i.e. something we can identify. Basically 2 traversals will give u the missing spot.

-> for(i=0;i<n;++i){
       if(array[i]<0) //is less than zero only when we set the duplicate to -1, look below
            continue;
       if array[i]==i+1   //in the right position
            continue;
       else{
            if(array[i]==array[array[i]-1]) //then its a duplicate, set it to -1
                 array[i] = -1
            else
                 swap(array[i],array[array[i]-1]) 
           }
    }
    //by the end of the above loop we have all elements in their corresponding positions and -1 in the place of the missing number
-> traverse the array and print out the position+1 of the the element with value == -1
//complexity analysis: no matter what the for loop will run 'n' times --> (n)
//traversal for finding the missing spot --> (n)
total complexity: O(n)

@Test public void findMissing()
{
int n=3;
int[] a=new int[n];
a[0]=2;a[1]=3;a[2]=3;

Hashtable m=new Hashtable();
for(int i=1;i<=n;i++)
{
m.put(i+"", i);
}

for(int i=0;i<a.length;i++)
{
if(m.containsKey(a[i]+""))
{
m.remove(a[i]+"");
}
}

//only one item left
System.out.println( m.values().iterator().next() );


}

#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[10]={1,2,3,4,5,6,7,2,9,10};
int sumr=(N*(N+1))/2,sumi=0,rpt,sumdiff;
for(int i=0;i<N;i++)
{sumi=sumi+a[i];
for(int j=i+1;j<N;j++)
{if(a[i]==a[j])rpt=a[i];
}
}
sumdiff=sumr-sumi;
printf("%d",rpt+sumdiff);
getch();
return 0;
}

xor would be the answer.
a xor a == 0;
for(numbers in array first to second last){
i xor i + 1
}

int flag =0;
int count =1;
int missing_num;
int a[n]; //the array with n numbers
int main()
{
while(flag =0)
{
for(int i=1;i<=n;i++)
{
if(count==a[i])
{
count++;
flag=0;
break;
}
else
{
missing_num = count;
flag=1;
}
}
}
printf("The missing number is: %d",missing_num);
return 0;
}

Does this solution seem good?

public static void repeatCheck(int[] a) {
		int pos = 1, temp=0;
		while(pos < a.length) {
			if(a[pos] >= 0) {
				if(a[a[pos]] < 0) {
					System.out.println("Repeated value: "+a[pos]);
					break;
				}
				temp = a[a[pos]];
				a[a[pos]] = -1;
				a[pos] = temp;
				System.out.println(Arrays.toString(a));
			}
			else
				pos++;
		}
	}