4 ms·
If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigati
by function_seven 8y ago
If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value.
You have to find your pointer in a circular linked list. But it’s only singly-linked, so you start just in front of it and work around the links the long way. 30% of the time, all the lists are 50 elements or shorter, meaning everyone is guaranteed to succeed.
- CamperBob2 8y agoBut what if your name is in box #51, which you aren't allowed to open?
- bewaretheirs 8y agoThen there's a cycle of length > 50 and everyone loses.
- function_seven 8y agoLike sibling says, this only happens when there’s a cycle longer than 50. In that case, you’re all doomed.