CareerCup

you want to find first missing number.

Negate the element on the index for current element. in the second loop check for positive number on an index& index is solution

for i=0;i<n;i++
a[a[i]-1] = -a[a[i]-1];

for i=0;i<n;++i
if(a[i] > 0)
printf("missing number is %d", i+1);

will there be more than one missing element.

Array containing Elements 1...n only? So you can put each element i in index i-1 and check again for those which aren't at their index.

Add the numbers given in that array. Let it be S. Subtract S from n*(n+1)/2. You will get the missing number.

Xor is better than sum.
n*(n+1)/2 may overflow, say when n is 1000,000 and you don't have 64 bit integer data type. Of course you can use double, but double has some precision problem.

Elements are repeated so summing or XORing will not work

import java.util.*;

public class NewClass {

public static void main(String[] args)
{
int [] arr = { 1, 2, 3, 3, 5, 6, 7};

int redundant = 0 ;
int arrSum = 0;
int peg = 0;
for (int i = 0; i< arr.length; i++)
{
if (arr[i] != i +1)
{
redundant = redundant + arr[i];
peg = i+1 - arr[i];
}
arrSum = arrSum + arr[i];
}
int realSum = arrSum - redundant;
int actualSum = (arr.length *(arr.length +1))/2;
int diff = actualSum - realSum;

System.out.println(String.format("Actual Sum = %d:: Real Sum = %d",actualSum, realSum));

System.out.println(String.format("Missing Number = %d",diff));
}

}

#include<stdio.h>
main( )
{
int arr[]= {2,1,8,5,4},arr_size,sub[100],i,ans;
arr_size=(sizeof(arr))/4;
for(i=0; i<arr_size; i++)
sub[i]=0;
ans=fun(&arr, &sub,arr_size);
printf("%d",ans);
}
int fun(int arr[ ], int sub[ ],int arr_size)
{
int val,i;
for(i=0; i<arr_size; i++)
{
val=arr[i];
if(((sub[val-1])==0)&&(val<=arr_size))
{
sub[val-1]=val;
}
else
{
for(i=0; i<arr_size; i++)
{
if(sub[i]==0)
return(i+1);
}
}
}
}

@all There can be more than one missing element also and are not sorted too..!!