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.
