Given a array, write a program to construct a triangle where last row contains elements of given array, every element of second last row contains sum of below two elements and so on.
Example 1:
Input:
A[] = {4, 7, 3, 6, 7};
Output:
81 40 41 21 19 22 11 10 9 13 4 7 3 6 7
Explanation:
       81
     40  41
   21  19  22
 11  10   9   13
4   7   3   6    7 
 
Example 2:
Input:
A[] = {5, 8, 1, 2, 4, 3, 14}
Output:
200 98 102 55 43 59 34 21 22 37 22
12 9 13 24 13 9 3 6 7 17 5 8 1 2 4 3 14 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function getTriangle() which takes the array A[] and its size N as inputs and returns the sum triangle.
 
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
 
Constraints:
1<=N<=1000
1<=Ai<=1000
Elements in the triangle will not exceed 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

def getTriangle( arr, n):
    
    



Solutions:
def getTriangle(arr, n):
	s = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		s[n - 1][i] = arr[i]
	j = 1
	while j < n:
		k = j
		for i in range(k, n, 1):
			s[n - 1 - j][i] = s[n - j][i] + s[n - j][i - 1]
		j += 1
	a = []
	i = n - 1
	while i > -1:
		for j in range(i, n, 1):
			a.append(s[n - 1 - i][j])
		i -= 1
	return a


def getTriangle(arr, n):
	temp = []
	ans = arr
	for i in range(n - 1):
		if len(arr) > 1:
			for j in range(len(arr) - 1):
				temp.append(arr[j] + arr[j + 1])
			ans = temp + ans
			arr = temp
			temp = []
		else:
			break
	return ans


def getTriangle(arr, n):
	arr.reverse()
	i = 1
	k = arr
	p = []
	m = arr
	while i < n:
		for d in range(n - i):
			j = k[d] + k[d + 1]
			p.append(j)
		m = m + p
		k[:] = p[:]
		p = []
		i = i + 1
	m.reverse()
	return m


def getTriangle(arr, n):
	ans = []

	def magic(arr, n, ans):
		if len(arr) == 1:
			ans.insert(0, [arr[0]])
			return
		ans.insert(0, arr)
		q = []
		for i in range(len(arr) - 1):
			q.append(arr[i] + arr[i + 1])
		arr = q.copy()
		magic(arr, n, ans)
	magic(arr, n, ans)
	w = []
	for i in ans:
		for j in i:
			w.append(j)
	return w


def getTriangle(arr, n):
	brr = [arr]
	while len(brr[-1]) > 1:
		brr.append([])
		for i in range(len(brr[-2]) - 1):
			brr[-1].append(brr[-2][i] + brr[-2][i + 1])
	output = []
	brr.reverse()
	for item in brr:
		output += item
	return output


def getTriangle(arr, n):
	dp = [[0 for i in range(n)] for j in range(n)]
	res = arr.copy()
	res = res[::-1]
	for i in range(n):
		dp[0][i] = arr[i]
	for i in range(1, n):
		temp = []
		for j in range(n - i):
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1]
			temp.append(dp[i][j])
		temp = temp[::-1]
		res.extend(temp)
	res = res[::-1]
	return res


def getTriangle(arr, n):
	p = arr
	s = []
	while len(p) > 1:
		t = []
		for index in range(len(p) - 1):
			t.append(p[index] + p[index + 1])
		s += t[::-1]
		p = t
	return s[::-1] + arr


def getTriangle(arr, n):
	ans = arr[::-1]
	while len(arr) > 1:
		ans1 = []
		for i in range(len(arr) - 1):
			ans1.append(arr[i] + arr[i + 1])
		ans.extend(ans1[::-1])
		arr = ans1
	return ans[::-1]


def getTriangle(arr, n):
	ans = []
	ans.append(arr)
	while len(ans[-1]) > 1:
		new = []
		for i in range(len(ans[-1]) - 1, 0, -1):
			new.append(ans[-1][i] + ans[-1][i - 1])
		ans.append(new[::-1])
	final = []
	for i in ans[::-1]:
		for j in i:
			final.append(j)
	return final


def getTriangle(arr, n):
	value = 0
	for i in range(0, n):
		value += n - i
	temp = [0] * value
	index = -1
	start = value - 1
	second = value - 2
	for i in range(0, n):
		sum = n - i
		if i >= 2:
			start -= 1
			second -= 1
		for j in range(sum):
			if i == 0:
				temp[index] = arr[n - j - 1]
				index -= 1
			else:
				temp[index] = temp[start] + temp[second]
				index -= 1
				start -= 1
				second -= 1
	return temp


def getTriangle(arr: list, n: int) -> list:
	if n < 2:
		return arr
	else:
		return getTriangle([arr[i] + arr[i + 1] for i in range(n - 1)], n - 1) + arr


def getTriangle(arr, n):
	d = [arr]
	for i in range(1, n):
		c = []
		for j in range(0, n - i):
			c.append(d[i - 1][j] + d[i - 1][j + 1])
		d.append(c)
	c = []
	d.reverse()
	for a in d:
		for b in a:
			c.append(b)
	return c


def getTriangle(arr, n):
	a = []
	a.append(arr)
	while len(arr) > 1:
		b = []
		for i in range(len(arr) - 1):
			b.append(arr[i] + arr[i + 1])
		a.append(b)
		arr = b
	c = []
	for i in reversed(a):
		for j in i:
			c.append(j)
	return c


def getTriangle(arr, n):
	ans = []

	def sumoftriangle(arr):
		if len(arr) == 1:
			return
		newarr = []
		prev = arr[0]
		for i in range(1, len(arr)):
			val = prev + arr[i]
			newarr.append(val)
			prev = arr[i]
		sumoftriangle(newarr)
		if newarr:
			ans.extend(newarr)
	sumoftriangle(arr)
	ans.extend(arr)
	return ans


def getTriangle(arr, n):
	a = arr
	y = a
	while len(y) >= 1:
		x = []
		for i in range(len(y) - 1):
			x.append(a[i] + a[i + 1])
		y = x
		a = x + a
	return a


def getTriangle(arr, n):
	z = []
	z.append(arr)
	while len(arr) > 1:
		temp = []
		for i in range(len(arr) - 1):
			temp.append(arr[i] + arr[i + 1])
		z.append(temp)
		arr = temp
	f = []
	for i in reversed(z):
		for j in i:
			f.append(j)
	return f


def getTriangle(a, n):

	def fun(a):
		b = []
		for i in range(len(a) - 1):
			b.append(a[i] + a[i + 1])
		return b
	c = a
	while len(fun(a)) > 0:
		b = fun(a)
		c = b + c
		a = b
	return c


def getTriangle(arr, n):
	if n == 1:
		return arr
	result = sol(arr, n, [])
	result.extend(arr)
	return result

def sol(arr, n, result):
	if n == 1:
		return arr
	temp = [0] * (n - 1)
	for i in range(n - 1):
		temp[i] = arr[i] + arr[i + 1]
	sol(temp, n - 1, result)
	result.extend(temp)
	return result


def getTriangle(arr, n):
	ans = []
	if len(arr) == 1:
		return arr
	else:
		l = []
		for i in range(len(arr) - 1):
			l.append(arr[i] + arr[i + 1])
		ans += getTriangle(l, len(l))
	return ans + arr


def getTriangle(arr, n):
	res = []
	prev = arr
	res.append(arr)
	for i in range(n):
		temp = []
		p = 0
		while p + 1 < len(prev):
			temp.append(prev[p] + prev[p + 1])
			p += 1
		res.append(temp)
		prev = temp
	res.reverse()
	t = ''
	tempo = []
	for i in res:
		if len(i):
			s = ' '.join(map(str, i))
			tempo.append(s)
	return tempo


def getTriangle(arr, n):
	tri = [[0 for i in range(n)] for i in range(n)]
	for i in range(n):
		tri[n - 1][i] = arr[i]
	i = n - 2
	while i >= 0:
		for j in range(0, i + 1, 1):
			tri[i][j] = tri[i + 1][j] + tri[i + 1][j + 1]
		i -= 1
	new_arr = []
	for i in range(n):
		for j in range(i + 1):
			new_arr.append(tri[i][j])
	return new_arr


def getTriangle(arr, n):
	f = arr[::-1]
	while len(arr) > 1:
		c = []
		for i in range(len(arr) - 1):
			c.append(arr[i] + arr[i + 1])
		f.extend(c[::-1])
		arr = c
	return f[::-1]


def getSumArray(temp):
	res = []
	for i in range(len(temp) - 1):
		total = temp[i] + temp[i + 1]
		res.append(total)
	return res

def getTriangle(arr, n):
	ans = arr[:]
	temp = ans[:]
	for i in range(n - 1):
		lst = getSumArray(temp)
		temp = lst[:]
		ans = lst + ans
	return ans


def getTriangle(arr, n):
	ans = arr[::-1]
	while len(arr) > 1:
		ans1 = []
		for i in range(len(arr) - 1):
			ans1.append(arr[i] + arr[i + 1])
		ans.extend(ans1[::-1])
		arr = ans1
	return ans[::-1]

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def getTriangle(arr, n):
	res = []
	res.append(arr)
	for i in range(1, n):
		ls = [0] * n
		res.append(ls)
	ret = []
	for i in range(1, n):
		ls1 = []
		for j in range(0, n - i):
			res[i][j] = res[i - 1][j] + res[i - 1][j + 1]
			if res[i][j] != 0:
				ls1.append(res[i][j])
		ret = ret + ls1[::-1]
	ret = ret[::-1] + arr
	return ret

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def getTriangle(arr, n):
	res = []
	a = arr
	i = 0
	r = []
	while len(arr) != 1:
		if i == len(arr) - 2:
			r.append(arr[i] + arr[i + 1])
			i = 0
			res.insert(0, r)
			arr = r
			r = []
			continue
		r.append(arr[i] + arr[i + 1])
		i += 1
	ress = []
	for x in res:
		ress.extend(x)
	ress.extend(a)
	return ress

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def getTriangle(arr, n):
	value = 0
	for i in range(0, n):
		value += n - i
	temp = [0] * value
	index = -1
	start = value - 1
	second = value - 2
	for i in range(0, n):
		sum = n - i
		if i >= 2:
			start -= 1
			second -= 1
		for j in range(sum):
			if i == 0:
				temp[index] = arr[n - j - 1]
				index -= 1
			else:
				temp[index] = temp[start] + temp[second]
				index -= 1
				start -= 1
				second -= 1
	return temp

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def getTriangle(arr, n):
	b = arr[::-1]
	while len(arr) != 1:
		c = []
		e = len(arr)
		for i in range(e - 1):
			c.append(arr[i] + arr[i + 1])
		b.extend(c[::-1])
		arr = c
	return b[::-1]

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def getTriangle(arr, n):
	if len(arr) == 1:
		return [arr[0]]
	current = arr.copy()
	current2 = []
	res = arr.copy()
	result = []
	while len(current) > 1:
		for itr in range(len(current) - 1):
			res.append(current[itr] + current[itr + 1])
			current2.append(current[itr] + current[itr + 1])
		current = current2.copy()
		current2 = []
	for itr in range(1, n + 1):
		temp = []
		for itr2 in range(itr):
			temp.append(res.pop())
		temp.reverse()
		for i in range(itr):
			result.append(temp[i])
	return result

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		Triangle = getTriangle(a, n)
		print(*Triangle)
		T -= 1
if __name__ == '__main__':
	main()


def recursive(arr, res, up):
	if res == [] and len(arr) == 1:
		return
	if len(arr) == 1:
		arr = res.copy()
		for i in res[::-1]:
			up.insert(0, i)
		res = []
	if len(arr) > 1:
		res.append(arr[0] + arr[1])
		recursive(arr[1:], res, up)
	li = map(str, up)
	return li

def getTriangle(arr, n):
	if n == 1:
		return [arr[0]]
	up = arr.copy()
	res = []
	li = recursive(arr, res, up)
	return li


def getTriangle(arr, n):
	x = n - 1
	ans = arr[::-1]
	i = 0
	j = 0
	while x > 0:
		if j < x:
			ans.append(ans[i] + ans[i + 1])
			i += 1
			j += 1
		else:
			i += 1
			x -= 1
			j = 0
	ans.reverse()
	return ans


def getTriangle(arr, n):

	def myfun(arr, n, l, res):
		if len(arr) == 1:
			return
		for i in range(n - 1):
			l.append(arr[i] + arr[i + 1])
		myfun(l, len(l), [], res)
		res.extend(l)
	l = []
	res = []
	myfun(arr, len(arr), l, res)
	res.extend(arr)
	return res


def getTriangle(arr, n):
	x = n
	res = []
	while x > 0:
		l = []
		t = [i for i in arr]
		for i in range(len(t) - 1):
			l.append(t[i] + t[i + 1])
		t = t[::-1]
		res.extend(t)
		arr = [i for i in l]
		x = x - 1
	return res[::-1]


def getTriangle(arr, n):
	if n == 1:
		return arr
	temp = []
	for i in range(n - 1):
		temp.append(arr[i] + arr[i + 1])
	arr = temp + arr
	return getTriangle(arr, n - 1)


def getTriangle(arr, n):
	temp2 = arr[::-1]
	while len(arr) > 1:
		temp1 = []
		for i in range(len(arr) - 1):
			temp1.append(arr[i] + arr[i + 1])
		temp2.extend(temp1[::-1])
		arr = temp1
	return temp2[::-1]


def getTriangle(arr, n):
	res = []
	res.append(arr)
	while len(arr) > 1:
		arr = sumofarray(arr)
		res.append(arr)
	res.reverse()
	result = []
	for i in range(len(res)):
		result += res[i]
	return result

def sumofarray(arr):
	i = 0
	j = 1
	res = []
	while j < len(arr):
		res.append(arr[i] + arr[j])
		i += 1
		j += 1
	return res


def getTriangle(arr, n):
	lst = []
	for j in range(n - 1, 0, -1):
		for i in range(j):
			lst.append(arr[i] + arr[i + 1])
		arr = lst + arr
		lst.clear()
	return arr


def getsum(arr, n, ans):
	if n < 1:
		return
	temp = []
	for i in range(n - 1):
		temp.append(arr[i] + arr[i + 1])
	getsum(temp, n - 1, ans)
	ans.extend(arr)

def getTriangle(arr, n):
	ans = []
	getsum(arr, n, ans)
	return ans


def getTriangle(arr, n):
	l = arr
	for i in range(n):
		l = [l[i] + l[i + 1] for i in range(len(l) - 1)]
		arr[:0] = l
	return arr


def getTriangle(arr, n):
	arr = arr[::-1]
	a = arr[::-1]
	fi = arr
	while len(a) > 1:
		z = []
		for i in range(len(a) - 1):
			z.append(a[i] + a[i + 1])
		arr.extend(z[::-1])
		a = z
	return arr[::-1]


def rec(a):
	x = []
	for i in range(len(a) - 1):
		sum = a[i] + a[i + 1]
		x.append(sum)
	return x

def getTriangle(arr, n):
	y = []
	y.append(arr)
	a = arr
	while n - 1 > 0:
		a = rec(a)
		y.append(a)
		n = n - 1
	x = []
	for i in y[::-1]:
		for j in i:
			x.append(j)
	return x


res = []

def solve(arr, n):
	global res
	if n < 1:
		return
	a = []
	for i in range(n - 1):
		a.append(arr[i] + arr[i + 1])
	res = a[:] + res
	solve(a, len(a))

def getTriangle(arr, n):
	global res
	res = arr[:]
	solve(arr, n)
	return res + ['']


def getTriangle(arr, n, ans=[]):
	if len(arr) == n:
		ans = []
	ans += arr[::-1]
	if len(arr) == 1:
		return ans[::-1]
	l = []
	track = arr[0]
	for i in arr[1:]:
		l.append(track + i)
		track = i
	return getTriangle(l, n, ans)


def getTriangle(arr, n):
	from collections import deque
	queue = deque(arr)
	finalList = []
	popCount = n
	while len(queue) > 1 and popCount > 1:
		tempList = []
		for i in range(1, popCount):
			el1 = queue.popleft()
			el2 = queue.popleft()
			nextSum = el1 + el2
			tempList.append(el1)
			queue.append(nextSum)
			if i != popCount - 1:
				queue.insert(0, el2)
			else:
				tempList.append(el2)
				tempList.extend(finalList)
				finalList = tempList
		popCount -= 1
	finalList.insert(0, queue.popleft())
	return finalList


import itertools

def getTriangle(arr, n):
	l = []
	l.append(arr)
	for i in range(n - 1):
		l_ist = []
		for j in range(len(arr) - 1):
			l_ist.append(arr[j] + arr[j + 1])
		l.append(l_ist)
		arr = l_ist.copy()
	l_rev = l[::-1]
	m = []
	for i in l_rev:
		m.extend(i)
	return m


def getTriangle(arr, n):
	l = arr
	for p in range(n, 1, -1):
		l2 = []
		for i in range(p - 1):
			l2.append(arr[i] + arr[i + 1])
		arr = l2
		l = l2 + l
	return l


def getTriangle(arr, n):
	final_ans = arr[::-1]
	while len(arr) > 1:
		curr_ans = []
		for i in range(len(arr) - 1):
			curr_ans.append(arr[i] + arr[i + 1])
		final_ans.extend(curr_ans[::-1])
		arr = curr_ans
	return final_ans[::-1]