More explanations on Solution #3 / Similarity to another interview question
In solution #3, we make a virtual white list by corresponding all the black numbers in the list to all the white numbers out of the list, where the virtual whit
In solution #3, we make a virtual white list by corresponding all the black numbers in the list to all the white numbers out of the list, where the virtual white list takes the first ```wlen``` (the length of white numbers = N - the length of black numbers) numbers starting from 0.\n\nTo guarantee a strict ONE-TO-ONE correspondence, we actually need to guarantee that the count of black numbers in the virtual list is exactly the same as the count of white numbers out of the virtual list.\n\nFor example, suppose ```N = 8``` and ```blacklist = {0, 2, 3, 6, 7}```. We first get ```wlen = N - blacklist.size = 8 - 5 = 3```. So the virtual list is the first 3 numbers starting from 0 (that is, ```0, 1, 2```). And, the correspondence and virtual white list looks like:\n```\n   virtual white list  |                rest list\n  0(b)   1(w)   2(b)   |   3(b)    4(w)    5(w)    6(b)   7(b)\n   |             |     |\n   v             v     |     count of black numbers in virtual white list = 2 = {0, 2}\n  4(w)          5(w)   |     count of white numbers in  the   rest   list = 2 = {4, 5}\n```\nNow, let\'s go back to our original concern: why the count of black numbers in the virtual list is exactly the same as the count of white numbers not in the virtual list.\n\nThis is acutally not difficult to answer, but this reminds me an old interview question: coins covered by cloth.\n\nThe question is like this:\nthere are ```1000``` coins on the table in front of you. It is known that ```20``` of them are head, and the others are tail. However, they are covered by some cloth, and the cloth is totally opaque, meaning that you cannot see which are head/tail. You are allowed to flip any number of coins you want, but you are not allowed to throw the cloth away. And, you cannot tell head/tail by touching them through the cloth. Could you find a method to separate all the coins into 2 groups, and each group has the same amount of head (the number of coins need not to be the same).\n\nThe answer is that you first choose any 20 coins to make a group (the other coins are another group), and flip all that 20 coins. Then the two groups have the same amount of head.\nWhy is it? Suppose there are originally ```x``` head in the 20 coins you choose, meaning that there are ```20-x``` coins in the 980-coin group. Now you flip all the 20 coins you choose, which makes all the ```x``` head into tail and all the ```20-x``` tail into head. Therefore, both groups now have ```20-x``` head.\n\nThis is the same logic why the count of black numbers in the virtual list is exactly the same as the count of white numbers not in the virtual list.\n\nThe following code is in C++ for this method (which is basically the same as solution #3).\n\n```\nclass Solution {\n    unordered_map<int, int> m;\n    int wlen;\npublic:\n    Solution(int N, vector<int>& blacklist) {\n        wlen = N - blacklist.size();\n        unordered_set<int> us;\n        for (int i = wlen; i < N; i++) us.insert(i);\n        for (int& x : blacklist) us.erase(x);\n        auto it = us.begin();\n        for (int& x : blacklist)\n            if (x < wlen) m[x] = *it++;\n    }\n    \n    int pick() {\n        int ret = rand() % wlen;\n        return m.count(ret) ? m[ret] : ret;\n    }\n};\n```
[]