Loading...
Loading...
Loading...
A chaining table starts with 4 buckets. A key goes to bucket key % capacity. Inserting a key that is already present changes nothing. After inserting a new key, if count > 0.75 * capacity, the capacity doubles and every stored key (including the new one) is placed again. Print three numbers: the final capacity, the total number of keys placed again over all doublings, and the length of the longest bucket at the end.
Example 1
Input
1 2 3 4 5 6 7
Output
16 11 1
The table doubles at the 4th key and at the 7th.
Example 2
Input
8 8 8
Output
4 0 1
Try the problem first. Open one hint at a time.
Track the count, the capacity and a running total of keys placed again.
At the end, build the buckets once and count the longest one.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor