Homework answers / question archive / Suppose that on your computer you have stored *n* password-protected files, each with a unique password

Suppose that on your computer you have stored *n* password-protected files, each with a unique password

Computer Science

Share With

Suppose that on your computer you have stored *n* password-protected files, each with a unique password. You’ve written down all of these *n* passwords, but you do not know which password unlocks which file. You’ve put these files into an array *F* and their passwords into an array *P* in an arbitrary order (so P[i] does not necessarily unlock F[i]). If you test password P[i] on file F[j], one of three things will happen: 1. P[i] unlocks F[j]. 2. The computer tells you that P[i] is lexicographically smaller than F[j]’s true password. 3. The computer tells you that P[i] is lexicographically greater than F[j]’s true password. You **cannot** test whether a password is lexicographically smaller or greater than another password, and you **cannot** test whether a file’s password is lexicographically smaller or greater than another file’s password. Design an algorithm to match each file to its password, which runs in expected runtime O(n log(n)).