I used one hour to solve the following problem. If you have solution too, welcome to share it here.
Given int N,
you are given array (1,2,3,…,N)
The array is permuted.
Now deleted one number and replace it with another number on list
e.g. if we replace i by j, there will be no "i" and two "j" in the list
You are given the modified array of size N.
Use a linearly time w/ const memory algorithm (you can read the array only; you cannot change the array) to find i and j
This problem reminds me one problem I met in my algorithm class in Stony Brook:
We have an array of n numbers. What we know is that there is one number occurring more than N/2 times in the array. Find the mode of these n numbers with linear time w/ constant memory algorithm.
2 則留言:
Just a thought for (1):
Compute sum{ a[i] } and compare with N(N+1)/2. Now you get j-i.
Compute sum{ a[i]^2 } and compare with N(N+1)(2N+1)/6. Now you get j^2-i^2.
Solve i & j from these 2 quantities.
(Assume multiplication & division are O(1).)
Yes, that's the first idea that I come up in my mind (I use sum and product, but essentially similar). And it is correct.
In practice, since N can be very large (say in order of 10^8; I think higher order is not so practical), so overflow problem may occur. To avoid this, one solution is using BigInteger. It is still linear, but the constant sounds too large... My friend who gave this problem to me points out this fact, so I use nearly one more hour to overcome this.
張貼留言