22
3
Upside-Down Pyramid Addition is the process of taking a list of numbers and consecutively adding them together until you reach one number.
When given the numbers 2, 1, 1
the following process occurs:
2 1 1
3 2
5
This ends in the number 5
.
YOUR TASK
Given the right side of an Upside-Down Pyramid (Ascending), write a program or function that will return the original list.
New Extra Challenge: Try doing this in less than O(n^2)
EXAMPLE
f([5, 2, 1]) => [2, 1, 1]
f([84,42,21,10,2]) => [4,7,3,8,2]
NOTE: The Upside-Down Pyramid will never be empty and will always consist of positive integers ONLY.
6
Welcome to PP&CG! This challenge is decent, though it could be improved. I'd recommend posting your challenges in the Sandbox first to improve the post before it's put on main.
– Tau – 2019-04-30T13:07:57.157Do the input and output have to be in the order given (top to bottom and left to right respectively), or can either or both be reversed? – Nick Kennedy – 2019-04-30T14:23:03.923
The input will go from bottom to top. The output must be from left to right – Whimpers – 2019-04-30T14:24:14.217
13Free insight that I can't find a language it's shorter in: $$f([a,b,c,d,e]) = \begin{bmatrix} 1&-4&6&-4&1 \ 0&1&-3&3&-1 \ 0&0&1&-2&1 \ 0&0&0&1&-1 \ 0&0&0&0&1 \end{bmatrix} \cdot \begin{bmatrix}a\b\c\d\e\end{bmatrix} $$ – Lynn – 2019-04-30T20:10:41.987
4
Just FYI, this is the same as the CodeWars kata.
– ggorlen – 2019-04-30T20:44:27.7406@ggorlen i know. I’m the one who made the kata :) – Whimpers – 2019-04-30T22:34:32.900
8
Try doing this in less than O(n)
surely it's impossible to allocate a n-sized array or change O(n) items in it faster than O(n) complexity? – my pronoun is monicareinstate – 2019-05-01T03:45:29.4173Suggested test case:
1 => 1
– Giuseppe – 2019-05-01T17:30:28.753@someone fixed, thanks for catching that, I meant quadratic time, not linear. – Whimpers – 2019-05-01T18:47:30.850