CareerCup

1. Store the index of the last element of the array (say in 'last').

2. Let x = rand()%M. x will be in [0,M-1] range. Output arr[x] and replace arr[x] with arr[last]. Do last--.

3. Repeat this step for N times, each time applying the mod operation with dividend one less than in the previous step i.e. rand()%(M-1), rand()%(M-2) and so on.

4. Time: O(N). Space: O(1).

5. In the above algorithm, you will be changing the array contents. If you want to maintain the array in the same state, you can keep track of all the changes you are making to the array and undo them after you printout the N values. This is better than making a copy of the array when M is large.

M=arr.size();
while(N>0){
        indx = rand()%M;
        swap(arr[indx],arr[M-1]);
        --N;-M;
} //the last N elements are the selected distinct integers//Time: O(N), Space : O(1)