Delta Encoding Savings

Problem

Compare raw fixed-width storage of a sorted list of non-negative integers against delta encoding, where the first value is stored relative to 0. Return saved bits, the sum of the bit lengths of the raw values minus the sum of the bit lengths of the consecutive differences. Return 0 for an empty list.

Hint

Sorted inputs have small gaps, so the differences need many fewer bits than the values.

Test cases

case 1

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

expected: 4

case 2

in: [[10,11,12]]

expected: 6

case 3

in: [[100,200,300]]

expected: 3

case 4

in: [[0,0,0]]

expected: 0

case 5

in: [[1,256,257]]

expected: 9

Starter codePython

def delta_encoding_savings(values):
    # Your code here
    pass

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