22
The difference list of a list of integers is the list differences of consecutive members.
For example the difference list of
1, 3, 2 ,4
is
2, -1, 2
Your task is to take as input a difference list and output what the difference list would look like if the original list were sorted.
For example the difference list
2, 1, -2, -1
Might represent a list
2 4 5 3 2
Which when sorted is
2 2 3 4 5
Which has a difference list of
0 1 1 1
This is code-golf so answers will be scored in bytes with less bytes being better.
Are solutions guaranteed to be unique? – H.PWiz – 2017-08-11T16:23:44.487
@H.PWiz Yes they are. – Post Rock Garf Hunter – 2017-08-11T16:23:57.127
Related. – totallyhuman – 2017-08-11T16:48:26.953
1@H.PWiz Quick proof: a list is perfectly reconstructable from a difference list (DL) combined with a first element value, so there's a one-to-one conversion from L to (FV, DL). Increasing the FV by any amount is the same as adding that amount to every element of the L and therefore it cannot change the sorting of L if that comparison is suitably monotonic. (In other words, it doesn't affect sorting unless the number you're adding causes integer overflow). – CR Drost – 2017-08-12T22:53:55.583
1Could you add a few more test cases? I notice some solutions giving differing outputs for
[-2, 100, -2, -1]
, for example. – Shaggy – 2017-08-14T10:14:54.760Does the output have to a list/array? Or can it just be a print of the difference values? – Goysa – 2017-08-14T14:44:10.190
@Goysa Any output that has the correct values in the right order is fine. – Post Rock Garf Hunter – 2017-08-14T14:49:36.910