Splay Rotation Count

Problem

Start with n nodes forming a right-leaning chain: node 0 is the root and node i has right child i + 1. Splay each accessed node to the root with bottom-up rotations: a zig is one rotation, a zig-zig or zig-zag is two. Return the total number of single rotations performed. Accesses are 0-based node ids.

Hint

A zig-zig rotates the parent first, a zig-zag rotates the node twice; both count as two single rotations.

Test cases

case 1

in: [3,[2]]

expected: 2

case 2

in: [4,[3]]

expected: 3

case 3

in: [5,[4,0]]

expected: 6

case 4

in: [1,[0]]

expected: 0

case 5

in: [4,[1,2,3]]

expected: 3

Starter codePython

def splay_rotation_count(n, accesses):
    # Your code here
    pass

5 test cases · run your code against them in the editor