Given a sorted integer array Arr[ ] of size N, and three integers A, B, and C. The task is to find a new array  where i^{th} element of the new array = A * Arr[i] * Arr[i] + B * Arr[i] + C where A ≠ 0. You have to print the new array in sorted (ascending) order.
Example 1:
Input:
A = -1, B = 2, C = -1.
N = 6
Arr[] = {-1, 0, 1, 2, 3, 4}
Output: 
-9 -4 -4 -1 -1 0
Explanation: After applying the equation 
A * Arr[i] * Arr[i] + B * Arr[i] + C on every 
element Arr[i] we get {-4, -1, 0, -1, -4, -9}.
After sorting, we get {-9, -4, -4, -1, -1, 0}. 
Example 2:
Input:
A = 1, B = 1, C = 1.
N = 3
Arr[] = {1, 2, 3}
Output: 
3 7 13
Explanation: After applying the equation
A * Arr[i] * Arr[i] + B * Arr[i] + C on every
element Arr[i] we get {3, 7, 13} which is 
already sorted.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sortArray() which takes Arr[], N, A, B and C as input parameters and returns the sorted new list.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}
-10^{5} ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Mathematics

Starter code: #User function Template for python3



class Solution:

	def sortArray(self, arr, n, A, B, C):

		# Code here

Solutions:
class Solution:

	def sortArray(self, arr, n, A, B, C):
		for i in range(n):
			arr[i] = A * arr[i] * arr[i] + B * arr[i] + C
		arr.sort()
		return arr


class Solution:

	def sortArray(self, arr, n, a, b, c):
		newarr = [0] * n
		for i in range(n):
			arr[i] = a * arr[i] * arr[i] + b * arr[i] + c
		if a >= 0:
			i = 0
			while i < n - 1:
				if arr[i + 1] > arr[i]:
					break
				i += 1
			k = i + 1
			j = i
			x = 0
			while j >= 0 and k < n:
				if arr[j] <= arr[k]:
					newarr[x] = arr[j]
					x += 1
					j -= 1
				else:
					newarr[x] = arr[k]
					k += 1
					x += 1
			while j >= 0:
				newarr[x] = arr[j]
				x += 1
				j -= 1
			while k < n:
				newarr[x] = arr[k]
				k += 1
				x += 1
			return newarr
		else:
			i = 0
			while i < n - 1:
				if arr[i + 1] < arr[i]:
					break
				i += 1
			k = n - 1
			j = 0
			x = 0
			while k >= i + 1 and j <= i:
				if arr[j] <= arr[k]:
					newarr[x] = arr[j]
					x += 1
					j += 1
				else:
					newarr[x] = arr[k]
					x += 1
					k -= 1
			while k >= i + 1:
				newarr[x] = arr[k]
				k -= 1
				x += 1
			while j <= i:
				newarr[x] = arr[j]
				x += 1
				j += 1
			return newarr


class Solution:

	def sortArray(self, arr, n, a, b, c):
		res = []
		E = lambda x: a * (x * x) + b * x + c
		for i in range(n):
			arr[i] = E(arr[i])
		index = 0
		if a > 0:
			for i in range(1, n):
				if arr[i] > arr[i - 1]:
					index = i - 1
					break
			j = index + 1
			while index > -1 and j < n:
				if arr[index] >= arr[j]:
					res.append(arr[j])
					j += 1
				else:
					res.append(arr[index])
					index -= 1
			while index > -1:
				res.append(arr[index])
				index -= 1
			while j < n:
				res.append(arr[j])
				j += 1
		else:
			for i in range(1, n):
				if arr[i] < arr[i - 1]:
					index = i - 1
					break
			(i, j) = (0, n - 1)
			while i <= index and j > index:
				if arr[i] >= arr[j]:
					res.append(arr[j])
					j -= 1
				else:
					res.append(arr[i])
					i += 1
			while i <= index:
				res.append(arr[i])
				i += 1
			while j > index:
				res.append(arr[j])
				j -= 1
		return res


class Solution:

	def sortArray(self, arr, n, A, B, C):
		result = []
		for i in range(n):
			res = A * arr[i] * arr[i] + B * arr[i] + C
			result.append(res)
		result.sort()
		return result


class Solution:

	def sortArray(self, arr, n, A, B, C):
		return sorted([A * x * x + b * x + C for x in arr])


class Solution:

	def sortArray(self, arr, n, A, B, C):
		y = []
		for i in arr:
			y.append(A * i ** 2 + B * i + C)
		y.sort()
		return y


class Solution:

	def sortArray(self, arr, n, A, B, C):
		c = []
		a1 = [A]
		b1 = [B]
		c1 = [C]
		for i in range(n):
			c.append(a1[0] * arr[i] * arr[i] + b1[0] * arr[i] + c1[0])
		return sorted(c)


class Solution:

	def sortArray(self, arr, n, A, B, C):
		lis = []
		for i in range(n):
			k = arr[i] * arr[i] * A + arr[i] * B + C
			lis.append(k)
		lis.sort()
		return lis


class Solution:

	def sortArray(self, arr, n, A, B, C):
		new_arr = []
		for i in range(n):
			ans = A * arr[i] * arr[i] + B * arr[i] + C
			new_arr.append(ans)
		new_arr.sort()
		return new_arr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		l = []
		for i in arr:
			c = A * i * i + B * i + C
			l.append(c)
		l.sort()
		return l


class Solution:

	def sortArray(self, Arr, n, A, B, C):
		l = []
		for i in range(n):
			l.append(A * Arr[i] * Arr[i] + B * Arr[i] + C)
		a = sorted(l)
		return a


class Solution:

	def sortArray(self, arr, n, A, B, C):
		return sorted(map(lambda x: A * x * x + B * x + C, arr))


class Solution:

	def sortArray(self, arr, n, A, B, C):
		l = []
		for i in range(0, n):
			v = A * arr[i] * arr[i] + (b * arr[i] + c)
			l.append(v)
		l = sorted(l)
		return l


class Solution:

	def sortArray(self, arr, n, A, B, C):
		arr = [A * i * i + B * i + C for i in arr]
		return sorted(arr)


class Solution:

	def sortArray(self, arr, n, A, B, C):
		ans = []
		for i in range(0, n):
			res = A * arr[i] * arr[i] + B * arr[i] + C
			ans.append(res)
		ans = sorted(ans)
		return ans


class Solution:

	def sortArray(self, arr, n, A, B, C):
		li = []
		for i in arr:
			li.append(A * i * i + B * i + C)
		li.sort()
		for i in li:
			return li


class Solution:

	def sortArray(self, arr, n, A, B, C):
		lst = []
		for i in range(0, len(arr)):
			lst.append(arr[i])
		arr.clear()
		for j in range(0, len(lst)):
			arr.append(A * lst[j] * lst[j] + B * lst[j] + C)
		arr.sort()
		return arr


class Solution:

	def f(self, A, B, C, x):
		return A * x ** 2 + B * x + C

	def sortArray(self, arr, n, A, B, C):
		sorted_arr = [0] * n
		x_optima = -B / (2 * A)
		idx = n
		for i in range(n):
			if arr[i] >= x_optima:
				idx = i
				break
		if A > 0:
			i = idx
			j = idx - 1
			c = 0
			while i < n and j >= 0:
				f_ai = self.f(A, B, C, arr[i])
				f_aj = self.f(A, B, C, arr[j])
				if f_ai <= f_aj:
					sorted_arr[c] = f_ai
					c += 1
					i += 1
				else:
					sorted_arr[c] = f_aj
					c += 1
					j -= 1
			while i < n:
				f_ai = self.f(A, B, C, arr[i])
				sorted_arr[c] = f_ai
				c += 1
				i += 1
			while j >= 0:
				f_aj = self.f(A, B, C, arr[j])
				sorted_arr[c] = f_aj
				c += 1
				j -= 1
		elif A < 0:
			j = 0
			i = n - 1
			c = 0
			while j < idx and i >= idx:
				f_ai = self.f(A, B, C, arr[i])
				f_aj = self.f(A, B, C, arr[j])
				if f_ai <= f_aj:
					sorted_arr[c] = f_ai
					c += 1
					i -= 1
				else:
					sorted_arr[c] = f_aj
					c += 1
					j += 1
			while i >= idx:
				f_ai = self.f(A, B, C, arr[i])
				sorted_arr[c] = f_ai
				c += 1
				i -= 1
			while j < idx:
				f_aj = self.f(A, B, C, arr[j])
				sorted_arr[c] = f_aj
				c += 1
				j += 1
		else:
			pass
		return sorted_arr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		arr1 = []
		for i in range(len(arr)):
			arr[i] = A * arr[i] * arr[i] + B * arr[i] + c
		arr1 = sorted(arr)
		return arr1


class Solution:

	def sortArray(self, arr, n, A, B, C):
		arr1 = list(map(lambda i: A * i * i + B * i + C, arr))
		return sorted(arr1)


class Solution:

	def sortArray(self, arr, n, A, B, C):
		reverse = False if A > 0 else True
		res = []
		for i in range(n):
			arr[i] = A * arr[i] * arr[i] + B * arr[i] + C
		if reverse:
			(i, j) = (0, n - 1)
			for z in range(1, n):
				if arr[z] < arr[z - 1]:
					x = z
					break
			while i < x and j >= x:
				if arr[i] < arr[j]:
					res.append(arr[i])
					i += 1
				else:
					res.append(arr[j])
					j -= 1
			while i < x:
				res.append(arr[i])
				i += 1
			while j > x + 1:
				res.append(arr[j])
				j -= 1
		else:
			(i, j) = (0, n - 1)
			for z in range(1, n):
				if arr[z] > arr[z - 1]:
					i = z - 1
					j = z
					break
			while i >= 0 and j < n:
				if arr[i] < arr[j]:
					res.append(arr[i])
					i -= 1
				else:
					res.append(arr[j])
					j += 1
			while i >= 0:
				res.append(arr[i])
				i -= 1
			while j < n:
				res.append(arr[j])
				j += 1
		return res


class Solution:

	def sortArray(self, arr, n, A, B, C):
		temp = []
		for i in arr:
			temp.append(A * i * i + B * i + c)
		temp.sort()
		for i in range(n):
			arr[i] = temp[i]
		return arr
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(a, b, c) = input().split()
		a = int(a)
		b = int(b)
		c = int(c)
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		ans = ob.sortArray(arr, n, a, b, c)
		for each in ans:
			print(each, end=' ')
		print()


class Solution:

	def equation(self, ele, A, B, C):
		return A * ele * ele + B * ele + C

	def sortArray(self, arr, n, A, B, C):
		if A != 0:
			z = -B / (2 * A)
			for i in range(n):
				if arr[i] >= z:
					break
			eq_arr = []
			if A > 0:
				j = i
				k = i - 1
				while j < n and k >= 0:
					e1 = self.equation(arr[j], A, B, C)
					e2 = self.equation(arr[k], A, B, C)
					if e1 >= e2:
						eq_arr.append(e2)
						k -= 1
					else:
						eq_arr.append(e1)
						j += 1
				while j < n:
					e1 = self.equation(arr[j], A, B, C)
					eq_arr.append(e1)
					j = j + 1
				while k >= 0:
					e2 = self.equation(arr[k], A, B, C)
					eq_arr.append(e2)
					k -= 1
			else:
				j = n - 1
				k = 0
				while j >= i and k < i:
					e1 = self.equation(arr[j], A, B, C)
					e2 = self.equation(arr[k], A, B, C)
					if e1 >= e2:
						eq_arr.append(e2)
						k += 1
					else:
						eq_arr.append(e1)
						j -= 1
				while j >= i:
					e1 = self.equation(arr[j], A, B, C)
					eq_arr.append(e1)
					j = j - 1
				while k < i:
					e2 = self.equation(arr[k], A, B, C)
					eq_arr.append(e2)
					k += 1
		return eq_arr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		l = [A * val ** 2 + B * val + C for val in arr]
		l.sort()
		return l


import heapq

class Solution:

	def sortArray(self, arr, n, A, B, C):
		(eql, out) = ([], [])
		for i in range(n):
			ans = A * arr[i] * arr[i] + B * arr[i] + C
			heapq.heappush(eql, ans)
		while len(eql) != 0:
			ans = heapq.heappop(eql)
			out.append(ans)
		return out


class Solution:

	def sortArray(self, arr, n, A, B, C):
		Arr = [0 for _ in range(n)]
		for i in range(n):
			Arr[i] = A * arr[i] * arr[i] + B * arr[i] + C
		Arr.sort()
		return Arr


class Solution:

	def sortArray(self, ar, n, a, b, c):
		d = []
		for i in ar:
			data = i * a * i + i * b + c
			d.append(data)
		d = sorted(d)
		return d


class Solution:

	def sortArray(self, arr, n, A, B, C):

		def compute(x):
			return A * x ** 2 + B * x + C
		pivot = -0.5 * B / A
		i = 0
		while i < n and arr[i] < pivot:
			i += 1
		j = i - 1
		ret = []
		while i < n and j > -1:
			if abs(pivot - arr[i]) > abs(pivot - arr[j]):
				ret.append(compute(arr[j]))
				j -= 1
			else:
				ret.append(compute(arr[i]))
				i += 1
		while i < n:
			ret.append(compute(arr[i]))
			i += 1
		while j > -1:
			ret.append(compute(arr[j]))
			j -= 1
		return ret if A > 0 else ret[::-1]


class Solution:

	def sortArray(self, arr, n, A, B, C):
		l = list()
		for i in range(len(arr)):
			l.append(A * arr[i] * arr[i] + B * arr[i] + C)
		l.sort()
		return l


class Solution:

	def sortArray(self, arr, n, A, B, C):
		new = [a * pow(i, 2) + b * i + c for i in arr]
		new.sort()
		return new


class Solution:

	def sortArray(self, arr, n, A, B, C):
		d = []
		for i in arr:
			res = a * i * i + i * B + c
			d.append(res)
		d.sort()
		return d


class Solution:

	def sortArray(self, arr, n, A, B, C):
		temp = [0] * n
		size = 0
		for i in range(0, n):
			arr[i] = A * arr[i] * arr[i] + B * arr[i] + C
		arr.sort()
		return arr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		temp = [0] * n
		size = 0
		for i in range(0, n):
			arr[i] = A * arr[i] * arr[i] + B * arr[i] + C
		breaking_point = -1
		if A < 0:
			for i in range(0, n - 1):
				if arr[i] > arr[i + 1]:
					breaking_point = i + 1
					break
			if breaking_point == -1:
				p1 = 0
				p2 = n
			else:
				p1 = 0
				p2 = n - 1
			while p1 <= breaking_point - 1 and p2 >= breaking_point:
				if arr[p1] <= arr[p2]:
					temp[size] = arr[p1]
					p1 += 1
					size += 1
				else:
					temp[size] = arr[p2]
					p2 -= 1
					size += 1
			while p1 <= breaking_point - 1:
				temp[size] = arr[p1]
				p1 += 1
				size += 1
			while p2 >= breaking_point:
				temp[size] = arr[p2]
				p2 -= 1
				size += 1
		else:
			for i in range(0, n - 1):
				if arr[i] < arr[i + 1]:
					breaking_point = i + 1
					break
			if breaking_point == -1:
				p1 = n - 1
				p2 = n
			else:
				p1 = breaking_point - 1
				p2 = breaking_point
			while p1 >= 0 and p2 < n:
				if arr[p1] <= arr[p2]:
					temp[size] = arr[p1]
					size += 1
					p1 -= 1
				else:
					temp[size] = arr[p2]
					size += 1
					p2 += 1
			while p1 >= 0:
				temp[size] = arr[p1]
				p1 -= 1
				size += 1
			while p2 < n:
				temp[size] = arr[p2]
				size += 1
				p2 += 1
		return temp


import math

class Solution:

	def findX(self, arr, n, x):
		(l, h) = (0, n - 1)
		while l <= h:
			m = l + (h - l >> 1)
			if arr[m] == x:
				return m
			elif arr[m] > x:
				h = m - 1
			else:
				l = m + 1
		return l

	def sortArray(self, arr, n, A, B, C):
		ans = []
		x = -B / (2 * A)
		p = self.findX(arr, n, x)
		if p <= 0 or p >= n - 1:
			for i in range(n):
				arr[i] = A * int(math.pow(arr[i], 2)) + B * arr[i] + C
			return arr
		if A > 0:
			(i, j) = (p, p - 1)
			while j >= 0 and i < n:
				if A * math.pow(arr[i], 2) + B * arr[i] + C <= A * math.pow(arr[j], 2) + B * arr[j] + C:
					ans.append(A * int(math.pow(arr[i], 2)) + B * arr[i] + C)
					i += 1
				else:
					ans.append(A * int(math.pow(arr[j], 2)) + B * arr[j] + C)
					j -= 1
			while j >= 0:
				ans.append(A * int(math.pow(arr[j], 2)) + B * arr[j] + C)
				j -= 1
			while i < n:
				ans.append(A * int(math.pow(arr[i], 2)) + B * arr[i] + C)
				i += 1
		else:
			(i, j) = (n - 1, 0)
			while j < p and i >= p:
				if A * math.pow(arr[i], 2) + B * arr[i] + C <= A * math.pow(arr[j], 2) + B * arr[j] + C:
					ans.append(A * int(math.pow(arr[i], 2)) + B * arr[i] + C)
					i -= 1
				else:
					ans.append(A * int(math.pow(arr[j], 2)) + B * arr[j] + C)
					j += 1
			while j < p:
				ans.append(A * int(math.pow(arr[j], 2)) + B * arr[j] + C)
				j += 1
			while i >= p:
				ans.append(A * int(math.pow(arr[i], 2)) + B * arr[i] + C)
				i -= 1
		return ans


class Solution:

	def sortArray(self, arr, n, A, B, C):
		n = len(arr)
		for i in range(0, n):
			tt = arr[i]
			arr[i] = A * (arr[i] * arr[i]) + B * arr[i] + C
		arr.sort()
		return arr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		arr2 = []
		for i in range(n):
			term = A * arr[i] * arr[i] + B * arr[i] + C
			arr2.append(term)
		arr2.sort()
		return arr2


class Solution:

	def sortArray(self, arr, n, A, B, C):
		arr1 = [None] * len(arr)
		for i in range(len(arr)):
			arr1[i] = A * arr[i] * arr[i] + B * arr[i] + C
		arr1.sort()
		return arr1


class Solution:

	def sortArray(self, arr, n, A, B, C):
		newArr = []
		for i in range(n):
			newArr.append(-1)
		for i in range(n):
			newArr[i] = a * arr[i] * arr[i] + b * arr[i] + c
		newArr.sort()
		return newArr


class Solution:

	def sortArray(self, arr, n, A, B, C):
		ans = []
		pivot = int(-(1 * B) / (2 * A))
		i = 0
		for i in range(n):
			if arr[i] >= pivot:
				break
		if A < 0:
			p1 = n - 1
			p2 = 0
			while p1 >= i and p2 < i:
				x = A * (arr[p1] * arr[p1]) + B * arr[p1] + C
				y = A * (arr[p2] * arr[p2]) + B * arr[p2] + C
				if x < y:
					ans.append(x)
					p1 -= 1
				else:
					ans.append(y)
					p2 += 1
			while p1 >= i:
				x = A * (arr[p1] * arr[p1]) + B * arr[p1] + C
				ans.append(x)
				p1 -= 1
			while p2 < i:
				x = A * (arr[p2] * arr[p2]) + B * arr[p2] + C
				ans.append(x)
				p2 += 1
		else:
			p1 = i
			p2 = i - 1
			while p1 < n and p2 >= 0:
				x = A * (arr[p1] * arr[p1]) + B * arr[p1] + C
				y = A * (arr[p2] * arr[p2]) + B * arr[p2] + C
				if x < y:
					ans.append(x)
					p1 += 1
				else:
					ans.append(y)
					p2 -= 1
			while p1 < n:
				x = A * (arr[p1] * arr[p1]) + B * arr[p1] + C
				ans.append(x)
				p1 += 1
			while p2 >= 0:
				x = A * (arr[p2] * arr[p2]) + B * arr[p2] + C
				ans.append(x)
				p2 -= 1
		return ans


class Solution:

	def sortArray(self, arr, n, A, B, C):
		for i in range(n):
			num = arr[i]
			arr[i] = A * num ** 2 + B * num + C
		return sorted(arr)


class Solution:

	def quadratic(self, a, b, c, x):
		return a * x ** 2 + b * x + c

	def sortArray(self, arr, n, A, B, C):
		return sorted([self.quadratic(A, B, C, x) for x in arr])