What is the probability that the array will remain the same?

Viewed 6780

This question has been asked in Microsoft interview. Very much curious to know why these people ask so strange questions on probability?

Given a rand(N), a random generator which generates random number from 0 to N-1.

int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
    int m = rand(N);
    int n = rand(N);
    swap(A[m],A[n]);
}

EDIT: Note that the seed is not fixed.

what is the probability that array A remains the same?
Assume that the array contains unique elements.

15 Answers
Related