CareerCup

I think what you can do is make a groups in array like if the size of array is 100 make 10 groups of 1-10 11-20 and so on. add 1-10 and compare them to sum of 1-10 from another array. similarly do for all other if the sum is not same you will left with small number of integers to compare. .

Two ways I can think of:
1) If you know that the numbers lie between 1 and some other known number, and if none of the numbers are repeated, then the sum of all those numbers should be n(n+1)/2 n being the last number.
Subtract this from the sum of the all elements in the array and you should get the number that is missing or repeated once.

2) Another way to do this is by using a bit-map vector. Algorithmically speaking, allocate a millions bits of space (10,00,000/8 bytes (10,00,000/8=char's)) and set to 0. For every number encountered in the input array, set the corresponding bit in the bit-map vector. Then do a linear scan through this bit-map vector and look for which entry is at 0, the corresponding number in the array is missing.

This method wont work if a number is repeated rather than missing in the input array.
Time complexity is O(n) and space complexity is excellent i.e- O(n) for n input array elements in bits.

Assuming integer 'a' is replaced with integer 'b'
Before replacement :-
sum of remaining integers + a = total sum (say c) -- eq 1
'xor of remaining integers' xor a = total xor (say d) -- eq 2

After replacement :-
sum of remaining integers + b = total sum (say e) -- eq 3
'xor of remaining integers' xor b = total xor (say f) -- eq 4

eq 1 substract eq 3 :-
a-b = c-e

eq 2 xor eq 4 :-
a xor b = d xor f

two variable, two equation. Hence problem solved

forgive me but I didn't quite understand the question.... anyone could give an example on a small array and elaborate the problem? Thank you much!

prevention is the best medicine :)

GSreplace(unsigned int index, int value)
  {
  UpdateLastReplaced(index);
  GSarray[index]= value;
  }

Should be binary search add all the elements of the first half of the two list compare it if it equal do the second part recursively the same else do first part recursively the same. this will end up with a complexity of O(log(n))

use the raid level concept...easy one in O(n)

If i have the Previous array with me say A[MILLION] and the new array is A'[]

then i can apply the following method:

For i = 1 to MILLION
{ set A[i] = A'[i] - A[i]
}

now scan through the array A[] , the only non zero entry will indicate the position of the changed element. Adding this to A'[i] will give you the original element as well.

complexity : N

*O(N)

Coder you rock