Kraft Inequality Slack

Problem

The Kraft sum for codeword lengths is sum(2^(-l)). Return the slack 1 - sum(2^(-l)), which is non-negative for a valid prefix-free length assignment and exactly 0 for a complete code. An empty length list has slack 1.0.

Hint

A complete binary prefix code uses all of the probability budget, leaving zero slack.

Test cases

case 1

in: [[1,1]]

expected: 0

case 2

in: [[2,2,2,2]]

expected: 0

case 3

in: [[1,2]]

expected: 0.25

case 4

in: [[3]]

expected: 0.875

case 5

in: [[]]

expected: 1

Starter codePython

def kraft_slack(lengths):
    # Your code here
    pass

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