CareerCup

generally solved by bit vector.

We can simply solve this using XOR technique.

a^a is always zero.

So we can initialize some variable say "value" as 1^2^3^....^k
And then for each element a[i] in the array do "value = value ^ a[i]"

So if initial array is {1,2,4} and K = 4
we'll do value = 1^2^3^4 ^ (1^2^4) = 3, which is the missing number.

Create an array a[k]. Initiaize it to zero. Now for each number encountered increment the value of the array by 1 i.e a[number]++. After all the billion records are traced, run a loop till k and print the index of array for which the value is 0. Thus, in this way we get the missing numbers. Whole operation reuires O(n)time.

If k<<N, then make a boolean array of 'k' elements. Scan the N-sized array and keep setting the corresponding value in the k-array to true. Then scan the k-array and the false values are the missing values.

this question can be done in O(1) space and in O(n) time too

1.scan the array from 1 to n one by one and as soon as you get a number(check absolute values of numbers) go to its index position and if the value stored in it is positive then multiply it by -1.

this way all the nos. which are present between 1-k would be having negative values stored in their indices while the numbers which are missing would be having positive values stored in their indices.

travel the array again from 1-k and print the value of indices that have positive values stored in it.

this works fine here as there are only positive integers present here :)

and also we save memory which was otherwise wasted in creating either Boolean or even array of size k

how many numbers are missing?
if it is one, xor.

There are several different solutions to the problem. Which one is better depends on how big the k is.

if i got the question correct then a number like
a=1000000000 t0 9999999999 so in this we have to just maintain an array of a[10]={0}
and then using modulo and division operator and mainting like
if
algo:
while(n)
{temp=n%10;
a[temp]=1;
n=n/10;
}
for(i=0;i<=9;i++)
{
if(!a[i])
{
printf("missing number");
}
}

Most of the above solutions are correct but the real catch lies in whether the problem is time-constrained or space-constrained. Array_sum or bit vector method concern space constraints ( O(n) vs 4-8bytes ), time constraint doesnt really matter since both methods take O(n) time. Can anybody think of a faster solution? say O(log n)?

O(log n) can be thought of if only 1 no is missing out of the given no from 1 to K.
By Binary Search.

If array is sorted and K < N:

{k(k+1)/2} - SumOf(1 to K-1),

Time complexcity: O(K)

If array is sorted and K < N:

{k(k+1)/2} - SumOf(1 to K-1),

Time complexity: O(K)

/// Using BitMap
#define SET_BIT(m, k) (m[k/8] |= (1 << (k % 8)))
#define IS_BIT_SET(m, k) (m[k/8] & (1 << (k % 8)))
#define CLR_BIT(m, k) (m[k/8] ^= (1 << (k % 8)))

int run()
{
const int ARRAY_SIZE = 1000;
int A[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i ++) A[i] = i + 1;
A[3] = 1; /// A[3] = 4, before
char * m = new char[ARRAY_SIZE/8 + 1];

memset(m, 0, ARRAY_SIZE/8 + 1);
for(int i = 0; i < ARRAY_SIZE; i ++) {
SET_BIT(m, A[i]);
}
for(int i = 1; i <= ARRAY_SIZE; i ++) {
if(IS_BIT_SET(m, i) == 0) printf("%d is missing\n", i);
}
delete [] m;
m = NULL;
return 0;
}

Please note that number lies between 1-k

1) store all the elements in array and find the sum of all array elements.
array_sum; /* Sum of all array elements */
2) sum = k * (k + 1); /* Sum of k elements */
3) missing_number = sum - array_sum;