The birthday clues
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- loops
- lists
- indexes
Problem
For Emiliano's eighth birthday, his aunt filled the backyard with shoe boxes numbered from 0, and inside each one she left a note with the number of the box to open next. Emiliano opens box 0 first, reads the note, goes to the box it names, and keeps going. The game ends when a note sends him to a box he already opened: that one does not count again.
You get notes, a list with at least one whole number: notes[i] is the number on the note in box i, always between 0 and the length minus 1, and it may be the same box. Several notes may send him to the same box, and some boxes may never be opened.
Return, as a whole number, how many different boxes Emiliano opened.
With [2, 0, 3, 1] he opens box 0, which sends him to 2; box 2 sends him to 3, box 3 to 1, and box 1 back to 0, which he already opened: you return 4.
With [1, 1, 0] he opens boxes 0 and 1, and box 1 sends him to itself: you return 2.
Examples
The example
[2, 0, 3, 1] → 4
A note that points to its own box
[1, 1, 0] → 2
A single box
[0] → 1
Two boxes stay closed
[1, 0, 3, 2] → 2
Back to a box in the middle
[1, 2, 3, 1, 0, 4] → 4
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def opened_boxes(notes):
passJavaScript
function openedBoxes(notes) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.